| 2000 | A Dual Version of Reimer's Inequality and a Proof of Rudich's Conjecture. Jeff Kahn, Michael E. Saks, Cliff Smyth |
| 2000 | A Lower Bound for the Shortest Path Problem. Ketan Mulmuley, Pradyut Shah |
| 2000 | A Separation of Determinism, Las Vegas and Nondeterminism for Picture Recognition. Pavol Duris, Juraj Hromkovic, Katsushi Inoue |
| 2000 | A Survey of Optimal PCP Characterizations of NP. Luca Trevisan |
| 2000 | An Application of Matroid Theory to the SAT Problem. Oliver Kullmann |
| 2000 | Average Case Complexity of Unbounded Fanin Circuits. Andreas Jakoby, Rüdiger Reischuk |
| 2000 | BP(L(f) Oliver Giel |
| 2000 | Characterization of Non-Deterministic Quantum Query and Quantum Communication Complexity. Ronald de Wolf |
| 2000 | Combinatorial Interpretation of Kolmogorov Complexity. Andrei Romashchenko, Alexander Shen, Nikolai K. Vereshchagin |
| 2000 | Computational Complexity and Phase Transitions. Gabriel Istrate |
| 2000 | Deciding the K-Dimension is PSPACE-Complete. Marcus Schaefer |
| 2000 | Dimension in Complexity Classes. Jack H. Lutz |
| 2000 | Easiness Assumptions and Hardness Tests: Trading Time for Zero Error. Valentine Kabanets |
| 2000 | Independent Minimum Length Programs to Translate between Given Strings. Nikolai K. Vereshchagin, Michael V. Vyugin |
| 2000 | Integer Circuit Evaluation is PSPACE-Complete. Ke Yang |
| 2000 | New Bounds for the Language Compression Problem. Harry Buhrman, Sophie Laplante, Peter Bro Miltersen |
| 2000 | On the Complexity of Intersecting Finite State Automata. George Karakostas, Richard J. Lipton, Anastasios Viglas |
| 2000 | On the Complexity of Quantum ACC. Frederic Green, Steven Homer, Chris Pollett |
| 2000 | On the Complexity of Some Problems on Groups Input as Multiplication Tables. David A. Mix Barrington, Peter Kadau, Klaus-Jörn Lange, Pierre McKenzie |
| 2000 | On the Complexity of the Monotonicity Verification. Andrei A. Voronenko |
| 2000 | On the Hardness of 4-Coloring a 3-Colorable Graph. Venkatesan Guruswami, Sanjeev Khanna |
| 2000 | Proceedings of the 15th Annual IEEE Conference on Computational Complexity, Florence, Italy, July 4-7, 2000 |
| 2000 | Quantum Kolmogorov Complexity. André Berthiaume, Wim van Dam, Sophie Laplante |
| 2000 | The Communication Complexity of Enumeration, Elimination, and Selection. Andris Ambainis, Harry Buhrman, William I. Gasarch, Bala Kalyanasundaram, Leen Torenvliet |
| 2000 | The Complexity of Tensor Calculus. Carsten Damm, Markus Holzer, Pierre McKenzie |
| 2000 | The Complexity of Verifying the Characteristic Polynomial and Testing Similarity. Thanh Minh Hoang, Thomas Thierauf |
| 2000 | The Query Complexity of Order-Finding. Richard Cleve |
| 2000 | Three Approaches to the Quantitative Definition of Information in an Individual Pure Quantum State. Paul M. B. Vitányi |
| 2000 | Time-Space Lower Bounds for SAT on Uniform and Non-Uniform Machines. Iannis Tourlakis |
| 2000 | Time-Space Tradeoffs for Nondeterministic Computation. Lance Fortnow, Dieter van Melkebeek |