default search action
23rd 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
- Harry Buhrman, John M. Hitchcock
:
NP-Hard Sets Are Exponentially Dense Unless coNP C NP/poly. 1-7 - Kord Eickmeyer
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
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
Generalized Tsirelson Inequalities, Commuting-Operator Provers, and Multi-prover Interactive Proof Systems. 187-198 - Andrew C. Doherty
The Quantum Moment Problem and Bounds on Entangled Multi-prover Games. 199-210 - Julia Kempe
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ý
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
manage site settings
To protect your privacy, all features that rely on external API calls from your browser are turned off by default. You need to opt-in for them to become active. All settings here will be stored as cookies with your web browser. For more information see our F.A.Q.
last updated on 2025-01-06 01:45 CET by the dblp team
all metadata released as open data under CC0 1.0 license
see also: Terms of Use | Privacy Policy | Imprint
dblp was originally created in 1993 at:
since 2018, dblp has been operated and maintained by:
the dblp computer science bibliography is funded and supported by: