| 2011 | Near-optimal distortion bounds for embedding doubling spaces into L | James R. Lee, Anastasios Sidiropoulos |
| 2011 | Pseudorandom generators for group products: extended abstract. | Michal Kouck, Prajakta Nimbhorkar, Pavel Pudlk |
| 2011 | High-rate codes with sublinear-time decoding. | Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin |
| 2011 | On the complexity of powering in finite fields. | Swastik Kopparty |
| 2011 | Moser and tardos meet Lovsz. | Kashyap Babu Rao Kolipaka, Mario Szegedy |
| 2011 | Mechanisms for (mis)allocating scientific credit. | Jon M. Kleinberg, Sigal Oren |
| 2011 | NP-hardness of approximately solving linear equations over reals. | Subhash Khot, Dana Moshkovitz |
| 2011 | Parallel repetition of entangled games. | Julia Kempe, Thomas Vidick |
| 2011 | A simpler algorithm and shorter proof for the graph minor decomposition. | Ken-ichi Kawarabayashi, Paul Wollan |
| 2011 | Breaking o(n | Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2011 | Deterministic construction of a high dimensional l | Zohar Shay Karnin |
| 2011 | Online bipartite matching with unknown distributions. | Chinmay Karande, Aranyak Mehta, Pushkar Tripathi |
| 2011 | The topology of wireless communication. | Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
| 2011 | Fast moment estimation in data streams in optimal space. | Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff |
| 2011 | Improved algorithms for min cut and max flow in undirected planar graphs. | Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen |
| 2011 | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. | Piotr Indyk, Eric Price |
| 2011 | Dueling algorithms. | Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, Moshe Tennenholtz |
| 2011 | The equivalence of the random oracle model and the ideal cipher model, revisited. | Thomas Holenstein, Robin Knzler, Stefano Tessaro |
| 2011 | Correlation testing for affine invariant properties on F | Hamed Hatami, Shachar Lovett |
| 2011 | Exact algorithms for solving stochastic games: extended abstract. | Kristoffer Arnsfelt Hansen, Michal Kouck, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas |
| 2011 | Analyzing network coding gossip made easy. | Bernhard Haeupler |
| 2011 | Privately releasing conjunctions and the statistical query barrier. | Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan R. Ullman |
| 2011 | Finding topological subgraphs is fixed-parameter tractable. | Martin Grohe, Ken-ichi Kawarabayashi, Dniel Marx, Paul Wollan |
| 2011 | Constant round non-malleable protocols using one way functions. | Vipul Goyal |
| 2011 | Pseudorandom generators for combinatorial shapes. | Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman |