2008 IEEE Conference on Computational Complexity (CCC 2008)

Accepted Papers

• 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 ZPP^SAT[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 ACC⁰ 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