| 2011 | Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP. | Yuichi Yoshida |
| 2011 | Near-optimal private approximation protocols via a black box transformation. | David P. Woodruff |
| 2011 | Submodular function maximization via the multilinear relaxation and contention resolution schemes. | Jan Vondrk, Chandra Chekuri, Rico Zenklusen |
| 2011 | Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. | Gregory Valiant, Paul Valiant |
| 2011 | Santa Claus schedules jobs on unrelated machines. | Ola Svensson |
| 2011 | Subspace embeddings for the L | Christian Sohler, David P. Woodruff |
| 2011 | Privacy-preserving statistical estimation with optimal convergence rates. | Adam D. Smith |
| 2011 | Strong direct product theorems for quantum communication and query complexity. | Alexander A. Sherstov |
| 2011 | Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. | Nitin Saxena, C. Seshadhri |
| 2011 | Distributed verification and hardness of distributed approximation. | Atish Das Sarma, Stephan Holzer, Liah Kor, Amos Korman, Danupon Nanongkai, Gopal Pandurangan, David Peleg, Roger Wattenhofer |
| 2011 | Black-box identity testing of depth-4 multilinear circuits. | Shubhangi Saraf, Ilya Volkovich |
| 2011 | Quantum one-way communication can be exponentially stronger than classical communication. | Oded Regev, Bo'az Klartag |
| 2011 | Don't rush into a union: take time to find your roots. | Mihai Patrascu, Mikkel Thorup |
| 2011 | The power of simple tabulation hashing. | Mihai Patrascu, Mikkel Thorup |
| 2011 | Limits of provable security from standard assumptions. | Rafael Pass |
| 2011 | On optimal single-item auctions. | Christos H. Papadimitriou, George Pierrakos |
| 2011 | An LLL-reduction algorithm with quasi-linear time complexity: extended abstract. | Andrew Novocin, Damien Stehl, Gilles Villard |
| 2011 | Every property of hyperfinite graphs is testable. | Ilan Newman, Christian Sohler |
| 2011 | A full derandomization of schning's k-SAT algorithm. | Robin A. Moser, Dominik Scheder |
| 2011 | Pareto optimal solutions for smoothed analysts. | Ankur Moitra, Ryan O'Donnell |
| 2011 | Fixed-parameter tractability of multicut parameterized by the size of the cutset. | Dniel Marx, Igor Razgon |
| 2011 | Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. | Mohammad Mahdian, Qiqi Yan |
| 2011 | Constant-round non-malleable commitments from any one-way function. | Huijia Lin, Rafael Pass |
| 2011 | How to leak on key updates. | Allison B. Lewko, Mark Lewko, Brent Waters |
| 2011 | Tight bounds for parallel randomized load balancing: extended abstract. | Christoph Lenzen, Roger Wattenhofer |