| 2011 | An | Jiawei Qian, David P. Williamson |
| 2011 | The Fourier Entropy-Influence Conjecture for Certain Classes of Boolean Functions. | Ryan O'Donnell, John Wright, Yuan Zhou |
| 2011 | On Minimal Unsatisfiability and Time-Space Trade-offs for | Jakob Nordstrm, Alexander A. Razborov |
| 2011 | Clique Clustering Yields a PTAS for max-Coloring Interval Graphs. | Tim Nonner |
| 2011 | Efficiently Decodable Error-Correcting List Disjunct Matrices and Applications - (Extended Abstract). | Hung Q. Ngo, Ely Porat, Atri Rudra |
| 2011 | Primal-Dual Approximation Algorithms for Node-Weighted Steiner Forest on Planar Graphs. | Carsten Moldenhauer |
| 2011 | Characterizing Arithmetic Circuit Classes by Constraint Satisfaction Problems - (Extended Abstract). | Stefan Mengel |
| 2011 | Online Graph Exploration: New Results on Old and New Algorithms. | Nicole Megow, Kurt Mehlhorn, Pascal Schweitzer |
| 2011 | Maximizing Polynomials Subject to Assignment Constraints. | Konstantin Makarychev, Maxim Sviridenko |
| 2011 | Improved Bounds for the Randomized Decision Tree Complexity of Recursive Majority. | Frdric Magniez, Ashwin Nayak, Miklos Santha, David Xiao |
| 2011 | Clustering with Local Restrictions. | Daniel Lokshtanov, Dniel Marx |
| 2011 | Isomorphism of Regular Trees and Words. | Markus Lohrey, Christian Mathissen |
| 2011 | Adaptively Secure Non-interactive Threshold Cryptosystems. | Benot Libert, Moti Yung |
| 2011 | A 1.488 Approximation Algorithm for the Uncapacitated Facility Location Problem. | Shi Li |
| 2011 | Constructing Differential Categories and Deconstructing Categories of Games. | Jim Laird, Giulio Manzonetto, Guy McCusker |
| 2011 | An Improved Approximation Algorithm for Minimum-Cost Subset | Bundit Laekhanukit |
| 2011 | Vertex Cover in Graphs with Locally Few Colors. | Fabian Kuhn, Monaldo Mastrolilli |
| 2011 | Restoring Pure Equilibria to Weighted Congestion Games. | Konstantinos Kollias, Tim Roughgarden |
| 2011 | On Stabilization in Herman's Algorithm. | Stefan Kiefer, Andrzej S. Murawski, Jol Ouaknine, James Worrell, Lijun Zhang |
| 2011 | Linear-Space Approximate Distance Oracles for Planar, Bounded-Genus and Minor-Free Graphs. | Ken-ichi Kawarabayashi, Philip N. Klein, Christian Sommer |
| 2011 | Relating Computational Effects by ⊤ ⊤-Lifting. | Shin-ya Katsumata |
| 2011 | Content Search through Comparisons. | Amin Karbasi, Stratis Ioannidis, Laurent Massouli |
| 2011 | Nondeterminism Is Essential in Small 2FAs with Few Reversals. | Christos A. Kapoutsis |
| 2011 | Robust Independence Systems. | Naonori Kakimura, Kazuhisa Makino |
| 2011 | Permanent Does Not Have Succinct Polynomial Size Arithmetic Circuits of Constant Depth. | Maurice J. Jansen, Rahul Santhanam |