| 2011 | Quantum Query Complexity of State Conversion. | Troy Lee, Rajat Mittal, Ben W. Reichardt, Robert Spalek, Mario Szegedy |
| 2011 | On Range Searching in the Group Model and Combinatorial Discrepancy. | Kasper Green Larsen |
| 2011 | A Nearly-m log n Time Solver for SDD Linear Systems. | Ioannis Koutis, Gary L. Miller, Richard Peng |
| 2011 | How to Play Unique Games Against a Semi-random Adversary: Study of Semi-random Models of Unique Games. | Alexandra Kolla, Konstantin Makarychev, Yury Makarychev |
| 2011 | A Two Prover One Round Game with Strong Soundness. | Subhash Khot, Muli Safra |
| 2011 | Delays and the Capacity of Continuous-Time Channels. | Sanjeev Khanna, Madhu Sudan |
| 2011 | The Minimum k-way Cut of Bounded Size is Fixed-Parameter Tractable. | Ken-ichi Kawarabayashi, Mikkel Thorup |
| 2011 | The Graph Minor Algorithm with Parity Conditions. | Ken-ichi Kawarabayashi, Bruce A. Reed, Paul Wollan |
| 2011 | New Extension of the Weil Bound for Character Sums with Applications to Coding. | Tali Kaufman, Shachar Lovett |
| 2011 | A Small PRG for Polynomial Threshold Functions of Gaussians. | Daniel M. Kane |
| 2011 | Evolution with Recombination. | Varun Kanade |
| 2011 | Testing and Reconstruction of Lipschitz Functions with Applications to Data Privacy. | Madhav Jha, Sofya Raskhodnikova |
| 2011 | A Parallel Approximation Algorithm for Positive Semidefinite Programming. | Rahul Jain, Penghui Yao |
| 2011 | On the Power of Adaptivity in Sparse Recovery. | Piotr Indyk, Eric Price, David P. Woodruff |
| 2011 | Algorithms for the Generalized Sorting Problem. | Zhiyi Huang, Sampath Kannan, Sanjeev Khanna |
| 2011 | 3-SAT Faster and Simpler - Unique-SAT Bounds for PPSZ Hold in General. | Timon Hertli |
| 2011 | Optimal Testing of Multivariate Polynomials over Small Prime Fields. | Elad Haramaty, Amir Shpilka, Madhu Sudan |
| 2011 | Coin Flipping with Constant Bias Implies One-Way Functions. | Iftach Haitner, Eran Omri |
| 2011 | Lasserre Hierarchy, Higher Eigenvalues, and Approximation Schemes for Graph Partitioning and Quadratic Integer Programming with PSD Objectives. | Venkatesan Guruswami, Ali Kemal Sinop |
| 2011 | Approximation Algorithms for Correlated Knapsacks and Non-martingale Bandits. | Anupam Gupta, Ravishankar Krishnaswamy, Marco Molinaro, R. Ravi |
| 2011 | Efficient Reconstruction of Random Multilinear Formulas. | Ankit Gupta, Neeraj Kayal, Satyanarayana V. Lokam |
| 2011 | Stateless Cryptographic Protocols. | Vipul Goyal, Hemanta K. Maji |
| 2011 | An FPTAS for #Knapsack and Related Counting Problems. | Parikshit Gopalan, Adam R. Klivans, Raghu Meka, Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda |
| 2011 | The Complexity of the Homotopy Method, Equilibrium Selection, and Lemke-Howson Solutions. | Paul W. Goldberg, Christos H. Papadimitriou, Rahul Savani |
| 2011 | A Randomized Rounding Approach to the Traveling Salesman Problem. | Shayan Oveis Gharan, Amin Saberi, Mohit Singh |