Accepted papers for CCC '04

Title: Abelian Permutation Group Problems and Logspace Counting Classes
Author(s): V. Arvind and T.C. Vijayaraghavan

Title: Compression of Samplable Sources
Author(s): Luca Trevisan, Salil Vadhan, and David Zuckerman

Title: Computing in fault tolerance broadcast networks
Author(s): Ilan Newman

Title: Consequences and Limits of Nonlocal Strategies
Author(s): R. Cleve and P. Hoyer and B. Toner and J. Watrous

Title: Deterministic Polynomial Identity Testing in Non Commutative Models
Author(s): Ran Raz, Amir Shpilka

Title: Dimension, Entropy Rates, and Compression
Author(s): John M. Hitchcock and N. V. Vinodchandran

Title: Graph properties and circular functions: how low can quantum query complexity go?
Author(s): Xiaoming Sun, Andrew C. Yao and Shengyu Zhang

Title: Language Compression and Pseudorandom Generators
Author(s): Harry Buhrman, Troy Lee, Dieter van Melkebeek

Title: Lower Bounds for Testing Bipartiteness in Dense Graphs
Author(s): Andrej Bogdanov, Luca Trevisan

Title: Lower bounds for randomized and quantum query complexity using Kolmogorov arguments
Author(s): Sophie Laplante and Frederic Magniez

Title: Multiparty Quantum Coin Flipping
Author(s): Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, and Hein Roehrig

Title: On Pseudoentropy versus Compressibility
Author(s): Hoeteck Wee

Title: On the power of Quantum Proofs
Author(s): Ran Raz, Amir Shpilka

Title: Parameterized complexity of constraint satisfaction problems
Author(s): Daniel Marx

Title: Partial bi-immunity and NP-completeness
Author(s): John M. Hitchcock, A. Pavan, N. V. Vinodchandran

Title: Polylogarithmic-round Interactive Proofs for coNP
Author(s): Alan L. Selman, Samik Sengupta

Title: Polynomials that Sign Represent Parity and Descartes Rule of Signs
Author(s): Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton

Title: Properties of NP-Complete Sets
Author(s): Christian Glasser, A. Pavan, Alan L. Selman, Samik Sengupta

Title: Quantum Arthur-Merlin Games
Author(s): Chris Marriott and John Watrous

Title: Reductions between Disjoint NP-Pairs
Author(s): Christian Glasser, Alan L. Selman, Samik Sengupta

Title: Relativized NP search problems and propositional proof systems
Author(s): Joshua Buresh-Oppenheim and Tsuyoshi Morioka

Title: Separating complexity classes using structural properties
Author(s): Harry Buhrman and Leen Torenvliet

Title: Small Spans in Scaled Dimension
Author(s): John M. Hitchcock

Title: Solvable Group Isomorphism is (almost) in NPcoNP
Author(s): V. Arvind and Jacobo Toran

Title: Some Results on Majority Quantifiers over words
Author(s): Klaus-Joern Lange

Title: The Complexity of Treelike Systems over λ-Local Formulae
Author(s): Nicola Galesi, Neil Thapen

Title: The Complexity of the Covering Radius Problem on Lattices and Codes
Author(s): Venkatesan Guruswami, Daniele Micciancio, Oded Regev

Title: Tight Lower Bounds for Certain Parameterized NP-hard Problems
Author(s): Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David Juedes, Iyad A. Kanj, Ge Xia

Title: Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information
Author(s): Andris Ambainis, Ke Yang

Title: Limitations of Quantum Advice and One-Way Communication
Author(s): Scott Aaronson