| 2011 | Linearizable implementations do not suffice for randomized distributed computation. | Wojciech M. Golab, Lisa Higham, Philipp Woelfel |
| 2011 | Optimal path search in small worlds: dimension matters. | George Giakkoupis, Nicolas Schabanel |
| 2011 | Separating succinct non-interactive arguments from all falsifiable assumptions. | Craig Gentry, Daniel Wichs |
| 2011 | A general framework for graph sparsification. | Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi |
| 2011 | Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. | Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick |
| 2011 | A unified framework for approximating and clustering data. | Dan Feldman, Michael Langberg |
| 2011 | Mechanism design with uncertain inputs: (to err is human, to forgive divine). | Uriel Feige, Moshe Tennenholtz |
| 2011 | From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking. | Omar Fawzi, Patrick M. Hayden, Pranab Sen |
| 2011 | From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. | Shaddin Dughmi, Tim Roughgarden, Qiqi Yan |
| 2011 | Social networks spread rumors in sublogarithmic time. | Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich |
| 2011 | Optimal auctions with correlated bidders are easy. | Shahar Dobzinski, Hu Fu, Robert D. Kleinberg |
| 2011 | An impossibility result for truthful combinatorial auctions with submodular valuations. | Shahar Dobzinski |
| 2011 | Directed spanners via flow-based linear programs. | Michael Dinitz, Robert Krauthgamer |
| 2011 | Cover times, blanket times, and majorizing measures. | Jian Ding, James R. Lee, Yuval Peres |
| 2011 | Contraction decomposition in h-minor-free graphs and algorithmic applications. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2011 | Inner product spaces for MinSum coordination mechanisms. | Richard Cole, Jos R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver |
| 2011 | An algorithm for the graph crossing number problem. | Julia Chuzhoy |
| 2011 | Electrical flows, laplacian systems, and faster approximation of maximum flow in undirected graphs. | Paul F. Christiano, Jonathan A. Kelner, Aleksander Madry, Daniel A. Spielman, Shang-Hua Teng |
| 2011 | Almost settling the hardness of noncommutative determinant. | Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan |
| 2011 | An optimal lower bound on the communication complexity of gap-hamming-distance. | Amit Chakrabarti, Oded Regev |
| 2011 | Geometric complexity theory and tensor rank. | Peter Brgisser, Christian Ikenmeyer |
| 2011 | Towards coding for maximum errors in interactive communication. | Mark Braverman, Anup Rao |
| 2011 | A quasipolynomial-time algorithm for the quantum separability problem. | Fernando G. S. L. Brando, Matthias Christandl, Jon Yard |
| 2011 | Multicut is FPT. | Nicolas Bousquet, Jean Daligault, Stphan Thomass |
| 2011 | Breaking the k | Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova |