| 2000 | Small Progress Measures for Solving Parity Games. | Marcin Jurdzinski |
| 2000 | Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem. | Klaus Jansen, Maxim Sviridenko |
| 2000 | Simulation and Bisimulation over One-Counter Processes. | Petr Jancar, Antonn Kucera, Faron Moller |
| 2000 | Two-Variable Word Equations. | Lucian Ilie, Wojciech Plandowski |
| 2000 | Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs. | Juraj Hromkovic, Martin Sauerhoff |
| 2000 | A New Algorithm for MAX-2-SAT. | Edward A. Hirsch |
| 2000 | A Classification of Symbolic Transition Systems. | Thomas A. Henzinger, Rupak Majumdar |
| 2000 | The Complexity of Poor Man's Logic. | Edith Hemaspaandra |
| 2000 | Fast Integer Sorting in Linear Space. | Yijie Han |
| 2000 | Spectral Bounds on General Hard Core Predicates. | Mikael Goldmann, Alexander Russell |
| 2000 | Languages of Dot-Depth 3/2. | Christian Glaer, Heinz Schmitz |
| 2000 | An Approximate L | Jessica H. Fong, Martin Strauss |
| 2000 | Decidability of Reachability Problems for Classes of Two Counters Automata. | Alain Finkel, Grgoire Sutre |
| 2000 | Characterizing and Deciding MSO-Definability of Macro Tree Transductions. | Joost Engelfriet, Sebastian Maneth |
| 2000 | The Hardness of Approximating Spanner Problems. | Michael Elkin, David Peleg |
| 2000 | On the Performance of WEAK-HEAPSORT. | Stefan Edelkamp, Ingo Wegener |
| 2000 | Real-Time Automata and the Kleene Algebra of Sets of Real Numbers. | Catalin Dima |
| 2000 | On the Many Faces of Block Codes. | Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta, B. Sundar Rajan |
| 2000 | The Power Range Assignment Problem in Radio Networks on the Plane. | Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri |
| 2000 | The Weighted 2-Server Problem. | Marek Chrobak, Jir Sgall |
| 2000 | Tilings: Recursivity and Regularity. | Julien Cervelle, Bruno Durand |
| 2000 | Optimal Proof Systems and Sparse Sets. | Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek |
| 2000 | Listing All Potential Maximal Cliques of a Graph. | Vincent Bouchitt, Ioan Todinca |
| 2000 | Randomness in Visual Cryptography. | Annalisa De Bonis, Alfredo De Santis |
| 2000 | lambda-Coloring of Graphs. | Hans L. Bodlaender, Ton Kloks, Richard B. Tan, Jan van Leeuwen |