23. CCC 2008: College Park, Maryland, USA

• Harry Buhrman, John M. Hitchcock:
  NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. 1-7
  
• 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
  
• Eric Allender, Michal Koucký:
  Amplifying Lower Bounds by Means of Self-Reducibility. 31-40
  
• Richard Chang, Suresh Purini:
  Amplifying ZPP^SAT[1] and the Two Queries Problem. 41-52
  
• Nati Linial, Adi Shraibman:
  Learning Complexity vs. Communication Complexity. 53-63
  
• Alexander A. Sherstov:
  Communication Complexity under Product and Nonproduct Distributions. 64-70
  
• Troy Lee, Adi Shraibman, Robert Spalek:
  A Direct Product Theorem for Discrepancy. 71-80
  
• 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
  
• Zeev Dvir, Amir Shpilka:
  Noisy Interpolating Sets for Low Degree Polynomials. 140-148
  
• 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
  
• Zeev Dvir, Amir Shpilka:
  Towards Dimension Expanders over Finite Fields. 304-310
  
• 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
  

Last update Tue May 22 04:49:10 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page