default search action
Google
Google Scholar
Semantic Scholar
Internet Archive Scholar
CiteSeerX
ORCID19th CCC 2004: Amherst, MA, USA
- 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA. IEEE Computer Society 2004, ISBN 0-7695-2120-7
Session 1
- Luca Trevisan, Salil P. Vadhan, David Zuckerman:
Compression of Samplable Sources. 1-14 - Harry Buhrman, Troy Lee, Dieter van Melkebeek:
Language Compression and Pseudorandom Generators. 15-28 - Hoeteck Wee:
On Pseudoentropy versus Compressibility. 29-41
Session 2
- Christian Glaßer, Alan L. Selman, Samik Sengupta:
Reductions between Disjoint NP-Pairs. 42-53 - Josh Buresh-Oppenheim, Tsuyoshi Morioka:
Relativized NP Search Problems and Propositional Proof Systems. 54-67 - Nicola Galesi, Neil Thapen:
The Complexity of Treelike Systems over lamda-Local Formulae. 68-74
Session 3
- Andrej Bogdanov, Luca Trevisan:
Lower Bounds for Testing Bipartiteness in Dense Graphs. 75-81 - Alan L. Selman, Samik Sengupta:
Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. 82-90 - Vikraman Arvind, Jacobo Torán:
Solvable Group Isomorphism. 91-103 - John M. Hitchcock:
Small Spans in Scaled Dimension. 104-112
Session 4
- Ilan Newman:
Computing in Fault Tolerance Broadcast Networks. 113-122 - Klaus-Jörn Lange:
Some Results on Majority Quantifiers over Words. 123-129 - Harry Buhrman, Leen Torenvliet:
Separating Complexity Classes Using Structural Properties. 130-138
Session 5
- Dániel Marx:
Parameterized Complexity of Constraint Satisfaction Problems. 139-149 - Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, Ge Xia:
Tight Lower Bounds for Certain Parameterized NP-Hard Problems. 150-160 - Venkatesan Guruswami, Daniele Micciancio
, Oded Regev:
The Complexity of the Covering Radius Problem on Lattices and Codes. 161-173
Session 6
- John M. Hitchcock, N. V. Vinodchandran:
Dimension, Entropy Rates, and Compression. 174-183 - Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta:
Properties of NP-Complete Sets. 184-197 - John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran:
Partial Bi-immunity and NP-Completeness. 198-203
Session 7
- Vikraman Arvind, T. C. Vijayaraghavan:
Abelian Permutation Group Problems and Logspace Counting Classes. 204-214 - Ran Raz, Amir Shpilka:
Deterministic Polynomial Identity Testing in Non-Commutative Models. 215-222 - Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton:
Polynomials That Sign Represent Parity and Descartes Rule of Signs. 223-235
Session 8
- Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous:
Consequences and Limits of Nonlocal Strategies. 236-249 - Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig:
Multiparty Quantum Coin Flipping. 250-259 - Ran Raz, Amir Shpilka:
On the Power of Quantum Proofs. 260-274 - Chris Marriott, John Watrous:
Quantum Arthur-Merlin Games. 275-285
Session 9
- Xiaoming Sun, Andrew Chi-Chih Yao, Shengyu Zhang:
Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? 286-293 - Sophie Laplante, Frédéric Magniez:
Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. 294-304 - Andris Ambainis, Ke Yang:
Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. 305-319 - Scott Aaronson:
Limitations of Quantum Advice and One-Way Communication. 320-332
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-12-09 23:25 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:
