| 2006 | 21st Annual IEEE Conference on Computational Complexity (CCC 2006), 16-20 July 2006, Prague, Czech Republic |
| 2006 | A 3-Query Non-Adaptive PCP with Perfect Completeness. Subhash Khot, Rishi Saket |
| 2006 | A Duality between Clause Width and Clause Density for SAT. Chris Calabro, Russell Impagliazzo, Ramamohan Paturi |
| 2006 | A Generic Time Hierarchy for Semantic Models with One Bit of Advice. Dieter van Melkebeek, Konstantin Pervyshev |
| 2006 | An Isomorphism between Subexponential and Parameterized Complexity Theory. Yijia Chen, Martin Grohe |
| 2006 | Applications of the Sum-Product Theorem in Finite Fields. Avi Wigderson |
| 2006 | Awards. |
| 2006 | Circuit Lower Bounds via Ehrenfeucht-Fraisse Games. Michal Koucký, Clemens Lautemann, Sebastian Poloczek, Denis Thérien |
| 2006 | Committees. |
| 2006 | Constructing Ramsey Graphs from Boolean Function Representations. Parikshit Gopalan |
| 2006 | Constructions of Low-Degree and Error-Correcting in-Biased Generators. Amir Shpilka |
| 2006 | Derandomization of Probabilistic Auxiliary Pushdown Automata Classes. H. Venkateswaran |
| 2006 | Distinguishing SAT from Polynomial-Size Circuits, through Black-Box Queries. Albert Atserias |
| 2006 | Every Linear Threshold Function has a Low-Weight Approximator. Rocco A. Servedio |
| 2006 | Exposure-Resilient Extractors. Marius Zimand |
| 2006 | FO[<]-Uniformity. Christoph Behle, Klaus-Jörn Lange |
| 2006 | Godel and Computations (Abstract). Pavel Pudlák |
| 2006 | Grid Graph Reachability Problems. Eric Allender, David A. Mix Barrington, Tanmoy Chakraborty, Samir Datta, Sambuddha Roy |
| 2006 | Hardness of the Covering Radius Problem on Lattices. Ishay Haviv, Oded Regev |
| 2006 | How to Get More Mileage from Randomness Extractors. Ronen Shaltiel |
| 2006 | Learning Monotone Decision Trees in Polynomial Time. Ryan O'Donnell, Rocco A. Servedio |
| 2006 | Making Hard Problems Harder. Joshua Buresh-Oppenheim, Rahul Santhanam |
| 2006 | Minimizing DNF Formulas and AC Eric Allender, Lisa Hellerstein, Paul McCabe, Toniann Pitassi, Michael E. Saks |
| 2006 | New Lower Bounds for Vertex Cover in the Lovasz-Schrijver Hierarchy. Iannis Tourlakis |
| 2006 | On Modular Counting with Polynomials. Kristoffer Arnsfelt Hansen |
| 2006 | On the Complexity of Numerical Analysis. Eric Allender, Peter Bürgisser, Johan Kjeldgaard-Pedersen, Peter Bro Miltersen |
| 2006 | Optimal Hardness Results for Maximizing Agreements with Monomials. Vitaly Feldman |
| 2006 | Oracles Are Subtle But Not Malicious. Scott Aaronson |
| 2006 | Parallel Repetition of Zero-Knowledge Proofs and the Possibility of Basing Cryptography on NP-Hardness. Rafael Pass |
| 2006 | Polynomial Identity Testing for Depth 3 Circuits. Neeraj Kayal, Nitin Saxena |
| 2006 | Preface. |
| 2006 | QMA/qpoly \subseteq PSPACE/poly: De-Merlinizing Quantum Protocols. Scott Aaronson |
| 2006 | Random Measurement Bases, Quantum State Distinction and Applications to the Hidden Subgroup Problem. Pranab Sen |
| 2006 | Reviewers. |
| 2006 | Strengths and Weaknesses of Quantum Fingerprinting. Dmitry Gavinsky, Julia Kempe, Ronald de Wolf |