List of accepted papers for CCC 2008: On the relative efficiency of resolution-like proofs and ordered binary decision diagram proofs Nathan Segerlind Exponential Separation of Quantum and Classical Non-Interactive Multi-Party Communication Complexity Dmitry Gavinsky and Pavel Pudlák Towards Dimension Expanders Over Finite Fields Zeev Dvir and Amir Shpilka Using Entanglement in Quantum Multi-Prover Interactive Proofs Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, and Thomas Vidick Communication Complexity Under Product and Nonproduct Distributions Alexander A. Sherstov Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions Alexander A. Sherstov Amplifying ZPPSAT[1] and the Two Queries Problem Richard Chang and Suresh Purini Amplifying Lower Bounds by Means of Self-Reducibility Eric Allender and Michal Koucký Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-in Zohar S. Karnin and Amir Shpilka The sum of d small-bias generators fools polynomials of degree d Emanuele Viola Learning complexity vs. communication complexity Nathan Linial and Adi Shraibman Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers Kiran S. Kedlaya and Sergey Yekhanin A direct product theorem for discrepancy Troy Lee, Adi Shraibman, and Robert Špalek The Multiplicative Quantum Adversary Robert Špalek Disjointness is hard in the multi-party number-on-the-forehead model Troy Lee and Adi Shraibman Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-Prover Interactive Proof Systems Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, and Andrew C.-C. Yao Approximisation of W[P]-complete minimisation problems is hard Kord Eickmeyer, Martin Grohe, and Magdalena Grüber Noisy Interpolating Sets for Low Degree Polynomials Zeev Dvir and Amir Shpilka Approximation Resistant Predicates From Pairwise Independence Per Austrin and Elchanan Mossel New results on Noncommutative and Commutative Polynomial Identity Testing V. Arvind, Partha Mukhopadhyay, and Srikanth Srinivasan Quantum Expanders: Motivation and Constructions Avraham Ben-Aroya, Oded Schwartz, and Amnon Ta-Shma Randomized Individual Communication Complexity Harry Buhrman, Michal Koucký, and Nikolai Vereshchagin 2-Transitivity is Insufficient for Local Testability Elena Grigorescu, Tali Kaufman, and Madhu Sudan Soft decoding, dual BCH codes, and better epsilon-biased list-decodable codes Venkatesan Guruswami and Atri Rudra Hardness amplification within NP against deterministic algorithms Parikshit Gopalan and Venkatesan Guruswami Constraint Logic: A Uniform Framework for Modeling Computation as Games Erik D. Demaine and Robert A. Hearn Lower Bounds and Separations for Constant Depth Multilinear Circuits Ran Raz and Amir Yehudayoff Detecting Rational Points on Hypersurfaces over Finite Fields Swastik Kopparty and Sergey Yekhanin NP-hard sets are exponentially dense unless coNP is contained in NP/poly Harry Buhrman and John M. Hitchcock The Power of Unentanglement Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, and Peter Shor Constant Width Planar Branching Programs Characterize ACC0 in Quasipolynomial Size Kristoffer Arnsfelt Hansen The quantum moment problem and bounds on entangled multiprover games Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, and Stephanie Wehner A Hypergraph Long Code Test with Perfect Completeness Victor Chen