Accepted papers for CCC '08

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 natural 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