| 2011 | A New Approach to Affine Extractors and Dispersers. Xin Li |
| 2011 | Approximation Algorithms for QMA-Complete Problems. Sevag Gharibian, Julia Kempe |
| 2011 | Bounded-Depth Circuits Cannot Sample Good Codes. Shachar Lovett, Emanuele Viola |
| 2011 | Derandomizing Polynomial Identity Testing for Multilinear Constant-Read Formulae. Matthew Anderson, Dieter van Melkebeek, Ilya Volkovich |
| 2011 | Explicit Dimension Reduction and Its Applications. Zohar Shay Karnin, Yuval Rabani, Amir Shpilka |
| 2011 | Hardness of Max-2Lin and Max-3Lin over Integers, Reals, and Large Cyclic Groups. Ryan O'Donnell, Yi Wu, Yuan Zhou |
| 2011 | Improved Constructions of Three Source Extractors. Xin Li |
| 2011 | Improved Direct Product Theorems for Randomized Query Complexity. Andrew Drucker |
| 2011 | Linear Systems over Finite Abelian Groups. Arkadev Chattopadhyay, Shachar Lovett |
| 2011 | Linear-Algebraic List Decoding of Folded Reed-Solomon Codes. Venkatesan Guruswami |
| 2011 | Lower Bounds on Query Complexity for Testing Bounded-Degree CSPs. Yuichi Yoshida |
| 2011 | Making Branching Programs Oblivious Requires Superlogarithmic Overhead. Paul Beame, Widad Machmouchi |
| 2011 | Near-Optimal and Explicit Bell Inequality Violations. Harry Buhrman, Oded Regev, Giannicola Scarpa, Ronald de Wolf |
| 2011 | Noisy Interpolation of Sparse Polynomials, and Applications. Shubhangi Saraf, Sergey Yekhanin |
| 2011 | Non-negatively Weighted #CSP: An Effective Complexity Dichotomy. Jin-Yi Cai, Xi Chen, Pinyan Lu |
| 2011 | Non-uniform ACC Circuit Lower Bounds. Ryan Williams |
| 2011 | On Arthur Merlin Games in Communication Complexity. Hartmut Klauck |
| 2011 | On the Minimal Fourier Degree of Symmetric Boolean Functions. Amir Shpilka, Avishay Tal |
| 2011 | On the Sum of Square Roots of Polynomials and Related Problems. Neeraj Kayal, Chandan Saha |
| 2011 | Paris-Harrington Tautologies. Lorenzo Carlucci, Nicola Galesi, Massimo Lauria |
| 2011 | Proceedings of the 26th Annual IEEE Conference on Computational Complexity, CCC 2011, San Jose, California, USA, June 8-10, 2011 |
| 2011 | Property Testing Lower Bounds via Communication Complexity. Eric Blais, Joshua Brody, Kevin Matulef |
| 2011 | Pseudorandom Generators for Combinatorial Checkerboards. Thomas Watson |
| 2011 | Pseudorandomness for Permutation and Regular Branching Programs. Anindya De |
| 2011 | Relativized Separations of Worst-Case and Average-Case Complexities for NP. Russell Impagliazzo |
| 2011 | Symmetric LDPC Codes are not Necessarily Locally Testable. Eli Ben-Sasson, Ghid Maatouk, Amir Shpilka, Madhu Sudan |
| 2011 | Symmetry of Information and Bounds on Nonuniform Randomness Extraction via Kolmogorov Extractors. Marius Zimand |
| 2011 | Symmetry-Assisted Adversaries for Quantum State Generation. Andris Ambainis, Loïck Magnin, Martin Roetteler, Jérémie Roland |
| 2011 | Tensor Rank: Some Lower and Upper Bounds. Boris Alexeev, Michael A. Forbes, Jacob Tsimerman |
| 2011 | Towards Lower Bounds on Locally Testable Codes via Density Arguments. Eli Ben-Sasson, Michael Viderman |
| 2011 | k-Independent Gaussians Fool Polynomial Threshold Functions. Daniel M. Kane |