| 2010 | A Log-Space Algorithm for Reachability in Planar Acyclic Digraphs with Few Sources. Derrick Stolee, Chris Bourke, N. V. Vinodchandran |
| 2010 | A New Sampling Protocol and Applications to Basing Cryptographic Primitives on the Hardness of NP. Iftach Haitner, Mohammad Mahmoody, David Xiao |
| 2010 | A Regularity Lemma, and Low-Weight Approximators, for Low-Degree Polynomial Threshold Functions. Ilias Diakonikolas, Rocco A. Servedio, Li-Yang Tan, Andrew Wan |
| 2010 | Communication Complexity with Synchronized Clocks. Russell Impagliazzo, Ryan Williams |
| 2010 | Completely Inapproximable Monotone and Antimonotone Parameterized Problems. Dániel Marx |
| 2010 | Derandomized Parallel Repetition Theorems for Free Games. Ronen Shaltiel |
| 2010 | Derandomized Parallel Repetition of Structured PCPs. Irit Dinur, Or Meir |
| 2010 | Derandomizing Arthur-Merlin Games and Approximate Counting Implies Exponential-Size Lower Bounds. Dan Gutfreund, Akinori Kawachi |
| 2010 | Derandomizing from Random Strings. Harry Buhrman, Lance Fortnow, Michal Koucký, Bruno Loff |
| 2010 | Exact Threshold Circuits. Kristoffer Arnsfelt Hansen, Vladimir V. Podolskii |
| 2010 | Fooling Functions of Halfspaces under Product Distributions. Parikshit Gopalan, Ryan O'Donnell, Yi Wu, David Zuckerman |
| 2010 | Lower Bounds for Testing Function Isomorphism. Eric Blais, Ryan O'Donnell |
| 2010 | No Strong Parallel Repetition with Entangled and Non-signaling Provers. Julia Kempe, Oded Regev |
| 2010 | On Matrix Rigidity and Locally Self-Correctable Codes. Zeev Dvir |
| 2010 | On the Matching Problem for Special Graph Classes. Thanh Minh Hoang |
| 2010 | On the Power of Randomized Reductions and the Checkability of SAT. Mohammad Mahmoody, David Xiao |
| 2010 | On the Relative Strength of Pebbling and Resolution. Jakob Nordström |
| 2010 | On the Unique Games Conjecture (Invited Survey). Subhash Khot |
| 2010 | Parallel Repetition of Two Prover Games (Invited Survey). Ran Raz |
| 2010 | Proceedings of the 25th Annual IEEE Conference on Computational Complexity, CCC 2010, Cambridge, Massachusetts, USA, June 9-12, 2010 |
| 2010 | Relationless Completeness and Separations. Pavel Hrubes, Avi Wigderson, Amir Yehudayoff |
| 2010 | Simple Affine Extractors Using Dimension Expansion. Matt DeVos, Ariel Gabizon |
| 2010 | Spectral Algorithms for Unique Games. Alexandra Kolla |
| 2010 | Symmetry Coincides with Nondeterminism for Time-Bounded Auxiliary Pushdown Automata. Eric Allender, Klaus-Jörn Lange |
| 2010 | The Gaussian Surface Area and Noise Sensitivity of Degree-d Polynomial Threshold Functions. Daniel M. Kane |
| 2010 | The Learning with Errors Problem (Invited Survey). Oded Regev |
| 2010 | The Partition Bound for Classical Communication Complexity and Query Complexity. Rahul Jain, Hartmut Klauck |
| 2010 | The Program-Enumeration Bottleneck in Average-Case Complexity Theory. Luca Trevisan |
| 2010 | Trade-Off Lower Bounds for Stack Machines. Matei David, Periklis A. Papakonstantinou |