| 2004 | 19th Annual IEEE Conference on Computational Complexity (CCC 2004), 21-24 June 2004, Amherst, MA, USA |
| 2004 | Abelian Permutation Group Problems and Logspace Counting Classes. Vikraman Arvind, T. C. Vijayaraghavan |
| 2004 | Compression of Samplable Sources. Luca Trevisan, Salil P. Vadhan, David Zuckerman |
| 2004 | Computing in Fault Tolerance Broadcast Networks. Ilan Newman |
| 2004 | Consequences and Limits of Nonlocal Strategies. Richard Cleve, Peter Høyer, Benjamin Toner, John Watrous |
| 2004 | Deterministic Polynomial Identity Testing in Non-Commutative Models. Ran Raz, Amir Shpilka |
| 2004 | Dimension, Entropy Rates, and Compression. John M. Hitchcock, N. V. Vinodchandran |
| 2004 | Graph Properties and Circular Functions: How Low Can Quantum Query Complexity Go? Xiaoming Sun, Andrew Chi-Chih Yao, Shengyu Zhang |
| 2004 | Language Compression and Pseudorandom Generators. Harry Buhrman, Troy Lee, Dieter van Melkebeek |
| 2004 | Limitations of Quantum Advice and One-Way Communication. Scott Aaronson |
| 2004 | Lower Bounds for Randomized and Quantum Query Complexity Using Kolmogorov Arguments. Sophie Laplante, Frédéric Magniez |
| 2004 | Lower Bounds for Testing Bipartiteness in Dense Graphs. Andrej Bogdanov, Luca Trevisan |
| 2004 | Multiparty Quantum Coin Flipping. Andris Ambainis, Harry Buhrman, Yevgeniy Dodis, Hein Röhrig |
| 2004 | On Pseudoentropy versus Compressibility. Hoeteck Wee |
| 2004 | On the Power of Quantum Proofs. Ran Raz, Amir Shpilka |
| 2004 | Parameterized Complexity of Constraint Satisfaction Problems. Dániel Marx |
| 2004 | Partial Bi-immunity and NP-Completeness. John M. Hitchcock, Aduri Pavan, N. V. Vinodchandran |
| 2004 | Polylogarithmic-Round Interactive Proofs for coNP Collapse the Exponential Hierarchy. Alan L. Selman, Samik Sengupta |
| 2004 | Polynomials That Sign Represent Parity and Descartes Rule of Signs. Saugata Basu, Nayantara Bhatnagar, Parikshit Gopalan, Richard J. Lipton |
| 2004 | Properties of NP-Complete Sets. Christian Glaßer, Aduri Pavan, Alan L. Selman, Samik Sengupta |
| 2004 | Quantum Arthur-Merlin Games. Chris Marriott, John Watrous |
| 2004 | Reductions between Disjoint NP-Pairs. Christian Glaßer, Alan L. Selman, Samik Sengupta |
| 2004 | Relativized NP Search Problems and Propositional Proof Systems. Josh Buresh-Oppenheim, Tsuyoshi Morioka |
| 2004 | Separating Complexity Classes Using Structural Properties. Harry Buhrman, Leen Torenvliet |
| 2004 | Small Spans in Scaled Dimension. John M. Hitchcock |
| 2004 | Solvable Group Isomorphism. Vikraman Arvind, Jacobo Torán |
| 2004 | Some Results on Majority Quantifiers over Words. Klaus-Jörn Lange |
| 2004 | The Complexity of Treelike Systems over lamda-Local Formulae. Nicola Galesi, Neil Thapen |
| 2004 | The Complexity of the Covering Radius Problem on Lattices and Codes. Venkatesan Guruswami, Daniele Micciancio, Oded Regev |
| 2004 | Tight Lower Bounds for Certain Parameterized NP-Hard Problems. Jianer Chen, Benny Chor, Mike Fellows, Xiuzhen Huang, David W. Juedes, Iyad A. Kanj, Ge Xia |
| 2004 | Towards the Classical Communication Complexity of Entanglement Distillation Protocols with Incomplete Information. Andris Ambainis, Ke Yang |