19. CCC 2004: Amherst, MA, USA

@proceedings{DBLP:conf/coco/2004,
  title     = {19th Annual IEEE Conference on Computational Complexity (CCC
               2004), 21-24 June 2004, Amherst, MA, USA},
  booktitle = {IEEE Conference on Computational Complexity},
  publisher = {IEEE Computer Society},
  year      = {2004},
  isbn      = {0-7695-2120-7},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

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
  

Last update Wed Feb 15 04:57:18 2012 CET by the DBLP Team — Data released under the ODC-BY 1.0 license — See also our legal information page