| 2005 | 20th Annual IEEE Conference on Computational Complexity (CCC 2005), 11-15 June 2005, San Jose, CA, USA |
| 2005 | A Direct Sum Theorem for Corruption and the Multiparty NOF Communication Complexity of Set Disjointness. Paul Beame, Toniann Pitassi, Nathan Segerlind, Avi Wigderson |
| 2005 | A Geometric Approach to Information-Theoretic Private Information Retrieval. David P. Woodruff, Sergey Yekhanin |
| 2005 | Average-Case Computations - Comparing AvgP, HP, and Nearly-P. Arfst Nickelsen, Birgit Schelm |
| 2005 | Awards. |
| 2005 | Better Time-Space Lower Bounds for SAT and Related Problems. Ryan Williams |
| 2005 | Bounded Color Multiplicity Graph Isomorphism is in the #L Hierarchy. Vikraman Arvind, Piyush P. Kurur, T. C. Vijayaraghavan |
| 2005 | Committees. |
| 2005 | Computationally Private Randomizing Polynomials and Their Applications. Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
| 2005 | Hardness of Max 3SAT with No Mixed Clauses. Venkatesan Guruswami, Subhash Khot |
| 2005 | If NP Languages are Hard on the Worst-Case Then It is Easy to Find Their Hard Instances. Dan Gutfreund, Ronen Shaltiel, Amnon Ta-Shma |
| 2005 | Monotone Circuits for Weighted Threshold Functions. Amos Beimel, Enav Weinreb |
| 2005 | More on Noncommutative Polynomial Identity Testing. Andrej Bogdanov, Hoeteck Wee |
| 2005 | NP with Small Advice. Lance Fortnow, Adam R. Klivans |
| 2005 | New Results on the Complexity of the Middle Bit of Multiplication. Ingo Wegener, Philipp Woelfel |
| 2005 | On Constructing Parallel Pseudorandom Generators from One-Way Functions. Emanuele Viola |
| 2005 | On the Complexity of Hardness Amplification. Chi-Jen Lu, Shi-Chun Tsai, Hsin-Lung Wu |
| 2005 | On the Complexity of Succinct Zero-Sum Games. Lance Fortnow, Russell Impagliazzo, Valentine Kabanets, Christopher Umans |
| 2005 | On the Fourier Spectrum of Symmetric Boolean Functions with Applications to Learning Symmetric Juntas. Richard J. Lipton, Evangelos Markakis, Aranyak Mehta, Nisheeth K. Vishnoi |
| 2005 | On the Hardness of Approximating Multicut and Sparsest-Cut. Shuchi Chawla, Robert Krauthgamer, Ravi Kumar, Yuval Rabani, D. Sivakumar |
| 2005 | On the Hardness of Distinguishing Mixed-State Quantum Computations. Bill Rosgen |
| 2005 | On the Ring Isomorphism and Automorphism Problems. Neeraj Kayal, Nitin Saxena |
| 2005 | On the Sensitivity of Cyclically-Invariant Boolean Functions. Sourav Chakraborty |
| 2005 | Preface. |
| 2005 | Prior Entanglement, Message Compression and Privacy in Quantum Communication. Rahul Jain, Jaikumar Radhakrishnan, Pranab Sen |
| 2005 | Pseudorandom Bits for Constant Depth Circuits with Few Arbitrary Symmetric Gates. Emanuele Viola |
| 2005 | Pseudorandomness for Approximate Counting and Sampling. Ronen Shaltiel, Christopher Umans |
| 2005 | Short PCPs Verifiable in Polylogarithmic Time. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan |
| 2005 | The Complexity of the Inertia and Some Closure Properties of GapL. Thanh Minh Hoang, Thomas Thierauf |
| 2005 | The Quantum Adversary Method and Classical Formula Size Lower Bounds. Sophie Laplante, Troy Lee, Mario Szegedy |
| 2005 | Tolerant Versus Intolerant Testing for Boolean Properties. Eldar Fischer, Lance Fortnow |
| 2005 | Topology Inside NC¹. Eric Allender, Samir Datta, Sambuddha Roy |
| 2005 | Toward a Model for Backtracking and Dynamic Programming. Michael Alekhnovich, Allan Borodin, Joshua Buresh-Oppenheim, Russell Impagliazzo, Avner Magen, Toniann Pitassi |
| 2005 | Upper Bounds for Quantum Interactive Proofs with Competing Provers. Gus Gutoski |