19. 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
- Harry Buhrman, Troy Lee, Dieter van Melkebeek: Language Compression and Pseudorandom Generators. 15-28
- Hoeteck Wee: On Pseudoentropy versus Compressibility. 29-41
Session 2
- Josh Buresh-Oppenheim, Tsuyoshi Morioka: Relativized NP Search Problems and Propositional Proof Systems. 54-67
Session 3
- Alan L. Selman, Samik Sengupta: Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. 82-90
- 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
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
- 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
- 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
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
data released under the ODC-BY 1.0 license. See also our legal information page
last updated on 2013-06-18T211851 by the dblp team