| 2008 | 2-Transitivity Is Insufficient for Local Testability. Elena Grigorescu, Tali Kaufman, Madhu Sudan |
| 2008 | A Direct Product Theorem for Discrepancy. Troy Lee, Adi Shraibman, Robert Spalek |
| 2008 | Amplifying Lower Bounds by Means of Self-Reducibility. Eric Allender, Michal Koucký |
| 2008 | Amplifying ZPP^SAT[1] and the Two Queries Problem. Richard Chang, Suresh Purini |
| 2008 | Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. Alexander A. Sherstov |
| 2008 | Approximation Resistant Predicates from Pairwise Independence. Per Austrin, Elchanan Mossel |
| 2008 | Approximation of Natural W[P]-Complete Minimisation Problems Is Hard. Kord Eickmeyer, Martin Grohe, Magdalena Grüber |
| 2008 | Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. Zohar Shay Karnin, Amir Shpilka |
| 2008 | Communication Complexity under Product and Nonproduct Distributions. Alexander A. Sherstov |
| 2008 | Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size. Kristoffer Arnsfelt Hansen |
| 2008 | Constraint Logic: A Uniform Framework for Modeling Computation as Games. Erik D. Demaine, Robert A. Hearn |
| 2008 | Detecting Rational Points on Hypersurfaces over Finite Fields. Swastik Kopparty, Sergey Yekhanin |
| 2008 | Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. Troy Lee, Adi Shraibman |
| 2008 | Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. Dmitry Gavinsky, Pavel Pudlák |
| 2008 | Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, Andrew Chi-Chih Yao |
| 2008 | Hardness Amplification within NP against Deterministic Algorithms. Parikshit Gopalan, Venkatesan Guruswami |
| 2008 | Learning Complexity vs. Communication Complexity. Nati Linial, Adi Shraibman |
| 2008 | Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. Kiran S. Kedlaya, Sergey Yekhanin |
| 2008 | Lower Bounds and Separations for Constant Depth Multilinear Circuits. Ran Raz, Amir Yehudayoff |
| 2008 | NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. Harry Buhrman, John M. Hitchcock |
| 2008 | New Results on Noncommutative and Commutative Polynomial Identity Testing. Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan |
| 2008 | Noisy Interpolating Sets for Low Degree Polynomials. Zeev Dvir, Amir Shpilka |
| 2008 | On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs. Nathan Segerlind |
| 2008 | Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA |
| 2008 | Quantum Expanders: Motivation and Constructions. Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma |
| 2008 | Randomised Individual Communication Complexity. Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin |
| 2008 | Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. Venkatesan Guruswami, Atri Rudra |
| 2008 | The Multiplicative Quantum Adversary. Robert Spalek |
| 2008 | The Power of Unentanglement. Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor |
| 2008 | The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, Stephanie Wehner |
| 2008 | The Sum of d Small-Bias Generators Fools Polynomials of Degree d. Emanuele Viola |
| 2008 | Towards Dimension Expanders over Finite Fields. Zeev Dvir, Amir Shpilka |
| 2008 | Using Entanglement in Quantum Multi-prover Interactive Proofs. Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick |