23. CCC 2008: College Park, Maryland, USA
Proceedings of the 23rd Annual IEEE Conference on Computational Complexity, CCC 2008, 23-26 June 2008, College Park, Maryland, USA. IEEE Computer Society 2008 ISBN 978-0-7695-3169-4- Kord Eickmeyer, Martin Grohe, Magdalena Grüber: Approximation of Natural W[P]-Complete Minimisation Problems Is Hard. 8-18
- Parikshit Gopalan, Venkatesan Guruswami: Hardness Amplification within NP against Deterministic Algorithms. 19-30
- Alexander A. Sherstov: Communication Complexity under Product and Nonproduct Distributions. 64-70
- Troy Lee, Adi Shraibman: Disjointness Is Hard in the Multi-party Number-on-the-Forehead Model. 81-91
- Kristoffer Arnsfelt Hansen: Constant Width Planar Branching Programs Characterize ACC^0 in Quasipolynomial Size. 92-99
- Nathan Segerlind: On the Relative Efficiency of Resolution-Like Proofs and Ordered Binary Decision Diagram Proofs. 100-111
- Alexander A. Sherstov: Approximate Inclusion-Exclusion for Arbitrary Symmetric Functions. 112-123
- Emanuele Viola: The Sum of d Small-Bias Generators Fools Polynomials of Degree d. 124-127
- Ran Raz, Amir Yehudayoff: Lower Bounds and Separations for Constant Depth Multilinear Circuits. 128-139
- Erik D. Demaine, Robert A. Hearn: Constraint Logic: A Uniform Framework for Modeling Computation as Games. 149-162
- Venkatesan Guruswami, Atri Rudra: Soft Decoding, Dual BCH Codes, and Better List-Decodable e-Biased Codes. 163-174
- Kiran S. Kedlaya, Sergey Yekhanin: Locally Decodable Codes From Nice Subsets of Finite Fields and Prime Factors of Mersenne Numbers. 175-186
- Tsuyoshi Ito, Hirotada Kobayashi, Daniel Preda, Xiaoming Sun, Andrew Chi-Chih Yao: Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. 187-198
- Andrew C. Doherty, Yeong-Cherng Liang, Ben Toner, Stephanie Wehner: The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. 199-210
- Julia Kempe, Hirotada Kobayashi, Keiji Matsumoto, Thomas Vidick: Using Entanglement in Quantum Multi-prover Interactive Proofs. 211-222
- Scott Aaronson, Salman Beigi, Andrew Drucker, Bill Fefferman, Peter W. Shor: The Power of Unentanglement. 223-236
- Robert Spalek: The Multiplicative Quantum Adversary. 237-248
- Per Austrin, Elchanan Mossel: Approximation Resistant Predicates from Pairwise Independence. 249-258
- Elena Grigorescu, Tali Kaufman, Madhu Sudan: 2-Transitivity Is Insufficient for Local Testability. 259-267
- Vikraman Arvind, Partha Mukhopadhyay, Srikanth Srinivasan: New Results on Noncommutative and Commutative Polynomial Identity Testing. 268-279
- Zohar Shay Karnin, Amir Shpilka: Black Box Polynomial Identity Testing of Generalized Depth-3 Arithmetic Circuits with Bounded Top Fan-In. 280-291
- Avraham Ben-Aroya, Oded Schwartz, Amnon Ta-Shma: Quantum Expanders: Motivation and Constructions. 292-303
- Swastik Kopparty, Sergey Yekhanin: Detecting Rational Points on Hypersurfaces over Finite Fields. 311-320
- Harry Buhrman, Michal Koucký, Nikolai K. Vereshchagin: Randomised Individual Communication Complexity. 321-331
- Dmitry Gavinsky, Pavel Pudlák: Exponential Separation of Quantum and Classical Non-interactive Multi-party Communication Complexity. 332-339
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-17T203624 by the dblp team