| 2011 | Slightly Superexponential Parameterized Problems. | Daniel Lokshtanov, Dniel Marx, Saket Saurabh |
| 2011 | Triangulating the Square and Squaring the Triangle: Quadtrees and Delaunay Triangulations are Equivalent. | Maarten Lffler, Wolfgang Mulzer |
| 2011 | Generalized Machine Activation Problems. | Jian Li, Samir Khuller |
| 2011 | Improved Deterministic Algorithms for Decremental Transitive Closure and Strongly Connected Components. | Jakub Lacki |
| 2011 | On LP-Based Approximability for Strict CSPs. | Amit Kumar, Rajsekar Manokaran, Madhur Tulsiani, Nisheeth K. Vishnoi |
| 2011 | The Matroid Median Problem. | Ravishankar Krishnaswamy, Amit Kumar, Viswanath Nagarajan, Yogish Sabharwal, Barna Saha |
| 2011 | Counting and detecting small subgraphs via equations and matrix multiplication. | Miroslaw Kowaluk, Andrzej Lingas, Eva-Marta Lundell |
| 2011 | The maximum size of a Sidon set contained in a sparse random set of integers. | Yoshiharu Kohayakawa, Sangjune Lee, Vojtech Rdl |
| 2011 | A Constant-Factor Approximation for Wireless Capacity Maximization with Power Control in the SINR Model. | Thomas Kesselheim |
| 2011 | Efficient algorithms for some special cases of the polynomial equivalence problem. | Neeraj Kayal |
| 2011 | The Rigidity Transition in Random Graphs. | Shiva Prasad Kasiviswanathan, Cristopher Moore, Louis Theran |
| 2011 | Top-K Color Queries for Document Retrieval. | Marek Karpinski, Yakov Nekrich |
| 2011 | Fast Convergence of Natural Bargaining Dynamics in Exchange Networks. | Yashodhan Kanoria, Mohsen Bayati, Christian Borgs, Jennifer T. Chayes, Andrea Montanari |
| 2011 | Range Selection and Median: Tight Cell Probe Lower Bounds and Adaptive Data Structures. | Allan Grnlund Jrgensen, Kasper Green Larsen |
| 2011 | Optimal Bounds for Johnson-Lindenstrauss Transforms and Streaming Problems with Sub-Constant Error. | T. S. Jayram, David P. Woodruff |
| 2011 | Secretary Problems: Laminar Matroid and Interval Scheduling. | Sungjin Im, Yajun Wang |
| 2011 | Online Scalable Algorithm for Minimizing ℓk-norms of Weighted Flow Time On Unrelated Machines. | Sungjin Im, Benjamin Moseley |
| 2011 | On Succinct Convex Greedy Drawing of 3-Connected Plane Graphs. | Xin He, Huaming Zhang |
| 2011 | The Dichotomy of List Homomorphisms for Digraphs. | Pavol Hell, Arash Rafiey |
| 2011 | Bayesian Incentive Compatibility via Matchings. | Jason D. Hartline, Robert Kleinberg, Azarakhsh Malekian |
| 2011 | Approximate Nearest Neighbor Search for Low Dimensional Queries. | Sariel Har-Peled, Nirman Kumar |
| 2011 | Wireless Capacity with Oblivious Power in General Metrics. | Magns M. Halldrsson, Pradipta Mitra |
| 2011 | Tight Bounds on the Approximability of Almost-satisfiable Horn SAT and Exact Hitting Set. | Venkatesan Guruswami, Yuan Zhou |
| 2011 | The complexity of finding independent sets in bounded degree (hyper)graphs of low chromatic number. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2011 | Pricing on Paths: A PTAS for the Highway Problem. | Fabrizio Grandoni, Thomas Rothvo |