| 2011 | A full derandomization of schöning's k-SAT algorithm. Robin A. Moser, Dominik Scheder |
| 2011 | A general framework for graph sparsification. Wai Shing Fung, Ramesh Hariharan, Nicholas J. A. Harvey, Debmalya Panigrahi |
| 2011 | A quasipolynomial-time algorithm for the quantum separability problem. Fernando G. S. L. Brandão, Matthias Christandl, Jon Yard |
| 2011 | A simpler algorithm and shorter proof for the graph minor decomposition. Ken-ichi Kawarabayashi, Paul Wollan |
| 2011 | A unified framework for approximating and clustering data. Dan Feldman, Michael Langberg |
| 2011 | Almost settling the hardness of noncommutative determinant. Steve Chien, Prahladh Harsha, Alistair Sinclair, Srikanth Srinivasan |
| 2011 | Almost tight bounds for reordering buffer management. Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Räcke |
| 2011 | An LLL-reduction algorithm with quasi-linear time complexity: extended abstract. Andrew Novocin, Damien Stehlé, Gilles Villard |
| 2011 | An algorithm for the graph crossing number problem. Julia Chuzhoy |
| 2011 | An impossibility result for truthful combinatorial auctions with submodular valuations. Shahar Dobzinski |
| 2011 | An optimal lower bound on the communication complexity of gap-hamming-distance. Amit Chakrabarti, Oded Regev |
| 2011 | Analyzing network coding gossip made easy. Bernhard Haeupler |
| 2011 | Approximate polytope membership queries. Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
| 2011 | Black-box identity testing of depth-4 multilinear circuits. Shubhangi Saraf, Ilya Volkovich |
| 2011 | Blackbox identity testing for bounded top fanin depth-3 circuits: the field doesn't matter. Nitin Saxena, C. Seshadhri |
| 2011 | Breaking o(n Ken-ichi Kawarabayashi, Yusuke Kobayashi |
| 2011 | Breaking the k Jean Bourgain, Stephen J. Dilworth, Kevin Ford, Sergei Konyagin, Denka Kutzarova |
| 2011 | Constant round non-malleable protocols using one way functions. Vipul Goyal |
| 2011 | Constant-round non-malleable commitments from any one-way function. Huijia Lin, Rafael Pass |
| 2011 | Contraction decomposition in h-minor-free graphs and algorithmic applications. Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2011 | Correlation testing for affine invariant properties on F Hamed Hatami, Shachar Lovett |
| 2011 | Cover times, blanket times, and majorizing measures. Jian Ding, James R. Lee, Yuval Peres |
| 2011 | Deterministic construction of a high dimensional l Zohar Shay Karnin |
| 2011 | Directed spanners via flow-based linear programs. Michael Dinitz, Robert Krauthgamer |
| 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 | Don't rush into a union: take time to find your roots. Mihai Patrascu, Mikkel Thorup |
| 2011 | Dueling algorithms. Nicole Immorlica, Adam Tauman Kalai, Brendan Lucier, Ankur Moitra, Andrew Postlewaite, Moshe Tennenholtz |
| 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 | Estimating the unseen: an n/log(n)-sample estimator for entropy and support size, shown optimal via new CLTs. Gregory Valiant, Paul Valiant |
| 2011 | Every property of hyperfinite graphs is testable. Ilan Newman, Christian Sohler |
| 2011 | Exact algorithms for solving stochastic games: extended abstract. Kristoffer Arnsfelt Hansen, Michal Koucký, Niels Lauritzen, Peter Bro Miltersen, Elias P. Tsigaridas |
| 2011 | Fast moment estimation in data streams in optimal space. Daniel M. Kane, Jelani Nelson, Ely Porat, David P. Woodruff |
| 2011 | Finding topological subgraphs is fixed-parameter tractable. Martin Grohe, Ken-ichi Kawarabayashi, Dániel Marx, Paul Wollan |
| 2011 | Fixed-parameter tractability of multicut parameterized by the size of the cutset. Dániel Marx, Igor Razgon |
| 2011 | From affine to two-source extractors via approximate duality. Noga Zewi, Eli Ben-Sasson |
| 2011 | From convex optimization to randomized mechanisms: toward optimal combinatorial auctions. Shaddin Dughmi, Tim Roughgarden, Qiqi Yan |
| 2011 | From low-distortion norm embeddings to explicit uncertainty relations and efficient information locking. Omar Fawzi, Patrick M. Hayden, Pranab Sen |
| 2011 | Geometric complexity theory and tensor rank. Peter Bürgisser, Christian Ikenmeyer |
| 2011 | High-rate codes with sublinear-time decoding. Swastik Kopparty, Shubhangi Saraf, Sergey Yekhanin |
| 2011 | How to leak on key updates. Allison B. Lewko, Mark Lewko, Brent Waters |
| 2011 | Improved algorithms for min cut and max flow in undirected planar graphs. Giuseppe F. Italiano, Yahav Nussbaum, Piotr Sankowski, Christian Wulff-Nilsen |
| 2011 | Inner product spaces for MinSum coordination mechanisms. Richard Cole, José R. Correa, Vasilis Gkatzelis, Vahab S. Mirrokni, Neil Olver |
| 2011 | K-median clustering, model-based compressive sensing, and sparse recovery for earth mover distance. Piotr Indyk, Eric Price |
| 2011 | Learning submodular functions. Maria-Florina Balcan, Nicholas J. A. Harvey |
| 2011 | Limits of provable security from standard assumptions. Rafael Pass |
| 2011 | Linearizable implementations do not suffice for randomized distributed computation. Wojciech M. Golab, Lisa Higham, Philipp Woelfel |
| 2011 | Mechanism design with uncertain inputs: (to err is human, to forgive divine). Uriel Feige, Moshe Tennenholtz |
| 2011 | Mechanisms for (mis)allocating scientific credit. Jon M. Kleinberg, Sigal Oren |
| 2011 | Moser and tardos meet Lovász. Kashyap Babu Rao Kolipaka, Mario Szegedy |
| 2011 | Multicut is FPT. Nicolas Bousquet, Jean Daligault, Stéphan Thomassé |
| 2011 | NP-hardness of approximately solving linear equations over reals. Subhash Khot, Dana Moshkovitz |
| 2011 | Near-optimal distortion bounds for embedding doubling spaces into L James R. Lee, Anastasios Sidiropoulos |
| 2011 | Near-optimal private approximation protocols via a black box transformation. David P. Woodruff |
| 2011 | On optimal single-item auctions. Christos H. Papadimitriou, George Pierrakos |
| 2011 | On the complexity of powering in finite fields. Swastik Kopparty |
| 2011 | Online bipartite matching with random arrivals: an approach based on strongly factor-revealing LPs. Mohammad Mahdian, Qiqi Yan |
| 2011 | Online bipartite matching with unknown distributions. Chinmay Karande, Aranyak Mehta, Pushkar Tripathi |
| 2011 | Optimal auctions with correlated bidders are easy. Shahar Dobzinski, Hu Fu, Robert D. Kleinberg |
| 2011 | Optimal constant-time approximation algorithms and (unconditional) inapproximability results for every bounded-degree CSP. Yuichi Yoshida |
| 2011 | Optimal path search in small worlds: dimension matters. George Giakkoupis, Nicolas Schabanel |
| 2011 | Parallel repetition of entangled games. Julia Kempe, Thomas Vidick |
| 2011 | Pareto optimal solutions for smoothed analysts. Ankur Moitra, Ryan O'Donnell |
| 2011 | Privacy-preserving statistical estimation with optimal convergence rates. Adam D. Smith |
| 2011 | Privately releasing conjunctions and the statistical query barrier. Anupam Gupta, Moritz Hardt, Aaron Roth, Jonathan R. Ullman |
| 2011 | Proceedings of the 43rd ACM Symposium on Theory of Computing, STOC 2011, San Jose, CA, USA, 6-8 June 2011 Lance Fortnow, Salil P. Vadhan |
| 2011 | Pseudorandom generators for combinatorial shapes. Parikshit Gopalan, Raghu Meka, Omer Reingold, David Zuckerman |
| 2011 | Pseudorandom generators for group products: extended abstract. Michal Koucký, Prajakta Nimbhorkar, Pavel Pudlák |
| 2011 | Quantum one-way communication can be exponentially stronger than classical communication. Oded Regev, Bo'az Klartag |
| 2011 | Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson |
| 2011 | Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni |
| 2011 | Santa Claus schedules jobs on unrelated machines. Ola Svensson |
| 2011 | Schaefer's theorem for graphs. Manuel Bodirsky, Michael Pinsker |
| 2011 | Secure computation with information leaking to an adversary. Miklós Ajtai |
| 2011 | Separating succinct non-interactive arguments from all falsifiable assumptions. Craig Gentry, Daniel Wichs |
| 2011 | Social networks spread rumors in sublogarithmic time. Benjamin Doerr, Mahmoud Fouz, Tobias Friedrich |
| 2011 | Strong direct product theorems for quantum communication and query complexity. Alexander A. Sherstov |
| 2011 | Subexponential lower bounds for randomized pivoting rules for the simplex algorithm. Oliver Friedmann, Thomas Dueholm Hansen, Uri Zwick |
| 2011 | Submodular function maximization via the multilinear relaxation and contention resolution schemes. Jan Vondrák, Chandra Chekuri, Rico Zenklusen |
| 2011 | Subspace embeddings for the L Christian Sohler, David P. Woodruff |
| 2011 | The computational complexity of linear optics. Scott Aaronson, Alex Arkhipov |
| 2011 | The equivalence of the random oracle model and the ideal cipher model, revisited. Thomas Holenstein, Robin Künzler, Stefano Tessaro |
| 2011 | The power of simple tabulation hashing. Mihai Patrascu, Mikkel Thorup |
| 2011 | The topology of wireless communication. Erez Kantor, Zvi Lotker, Merav Parter, David Peleg |
| 2011 | Tight bounds for parallel randomized load balancing: extended abstract. Christoph Lenzen, Roger Wattenhofer |
| 2011 | Towards coding for maximum errors in interactive communication. Mark Braverman, Anup Rao |