| 2000 | A Classification of Symbolic Transition Systems. Thomas A. Henzinger, Rupak Majumdar |
| 2000 | A New Algorithm for MAX-2-SAT. Edward A. Hirsch |
| 2000 | About Cube-Free Morphisms. Gwénaël Richomme, Francis Wlazinski |
| 2000 | Almost Complete Sets. Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn |
| 2000 | An Approximate L Jessica H. Fong, Martin Strauss |
| 2000 | An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications. Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude König |
| 2000 | An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality. Hans-Joachim Böckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger |
| 2000 | Average-Case Quantum Query Complexity. Andris Ambainis, Ronald de Wolf |
| 2000 | Bias Invariance of Small Upper Spans. Jack H. Lutz, Martin Strauss |
| 2000 | Binary Exponential Backoff Is Stable for High Arrival Rates. Hesham Al-Ammal, Leslie Ann Goldberg, Philip D. MacKenzie |
| 2000 | Characterizing and Deciding MSO-Definability of Macro Tree Transductions. Joost Engelfriet, Sebastian Maneth |
| 2000 | Circuits versus Trees in Algebraic Complexity. Pascal Koiran |
| 2000 | Codes and Graphs. Mohammad Amin Shokrollahi |
| 2000 | Controlled Conspiracy-2 Search. Ulf Lorenz |
| 2000 | Decidability of Reachability Problems for Classes of Two Counters Automata. Alain Finkel, Grégoire Sutre |
| 2000 | Distance Labeling Schemes for Well-Separated Graph Classes. Michal Katz, Nir A. Katz, David Peleg |
| 2000 | Fast Integer Sorting in Linear Space. Yijie Han |
| 2000 | Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. Vikraman Arvind, Johannes Köbler |
| 2000 | Hard Instances of Hard Problems. Jack H. Lutz, Vikram Mhetre, Sridhar Srinivasan |
| 2000 | Hereditary History Preserving Bisimilarity Is Undecidable. Marcin Jurdzinski, Mogens Nielsen |
| 2000 | Languages of Dot-Depth 3/2. Christian Glaßer, Heinz Schmitz |
| 2000 | Linear Cellular Automata with Multiple State Variables. Jarkko Kari |
| 2000 | Listing All Potential Maximal Cliques of a Graph. Vincent Bouchitté, Ioan Todinca |
| 2000 | Logics Capturing Local Properties. Leonid Libkin |
| 2000 | Multi-linearity Self-Testing with Relative Error. Frédéric Magniez |
| 2000 | Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. Vikraman Arvind, Johannes Köbler, Martin Mundhenk, Jacobo Torán |
| 2000 | On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem. Yair Bartal, Elias Koutsoupias |
| 2000 | On the Many Faces of Block Codes. Kaustubh Deshmukh, Priti Shankar, Amitava Dasgupta, B. Sundar Rajan |
| 2000 | On the Performance of WEAK-HEAPSORT. Stefan Edelkamp, Ingo Wegener |
| 2000 | On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers. Luca Aceto, Zoltán Ésik, Anna Ingólfsdóttir |
| 2000 | Online Dial-a-Ride Problems: Minimizing the Completion Time. Norbert Ascheuer, Sven Oliver Krumke, Jörg Rambau |
| 2000 | Optimal Proof Systems and Sparse Sets. Harry Buhrman, Stephen A. Fenner, Lance Fortnow, Dieter van Melkebeek |
| 2000 | Polynomial Time Approximation Schemes for the Multiprocessor Open and Flow Shop Scheduling Problem. Klaus Jansen, Maxim Sviridenko |
| 2000 | Pruning Graphs with Digital Search Trees. Application to Distance Hereditary Graphs. Jean-Marc Lanlignel, Olivier Raynaud, Eric Thierry |
| 2000 | Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures. Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini |
| 2000 | Randomness in Visual Cryptography. Annalisa De Bonis, Alfredo De Santis |
| 2000 | Real-Time Automata and the Kleene Algebra of Sets of Real Numbers. Catalin Dima |
| 2000 | STACS 2000, 17th Annual Symposium on Theoretical Aspects of Computer Science, Lille, France, February 2000, Proceedings Horst Reichel, Sophie Tison |
| 2000 | Simulation and Bisimulation over One-Counter Processes. Petr Jancar, Antonín Kucera, Faron Moller |
| 2000 | Small Progress Measures for Solving Parity Games. Marcin Jurdzinski |
| 2000 | Spectral Bounds on General Hard Core Predicates. Mikael Goldmann, Alexander Russell |
| 2000 | Succinct Representations of Model Based Belief Revision. Paolo Penna |
| 2000 | The Boolean Hierarchy of NP-Partitions. Sven Kosub, Klaus W. Wagner |
| 2000 | The CNN Problem and Other k-Server Variants. Elias Koutsoupias, David Scot Taylor |
| 2000 | The Complexity of Planarity Testing. Eric Allender, Meena Mahajan |
| 2000 | The Complexity of Poor Man's Logic. Edith Hemaspaandra |
| 2000 | The Data Broadcast Problem with Preemption. Nicolas Schabanel |
| 2000 | The Hardness of Approximating Spanner Problems. Michael Elkin, David Peleg |
| 2000 | The Power Range Assignment Problem in Radio Networks on the Plane. Andrea E. F. Clementi, Paolo Penna, Riccardo Silvestri |
| 2000 | The Stability of Saturated Linear Dynamical Systems Is Undecidable. Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis |
| 2000 | The Weighted 2-Server Problem. Marek Chrobak, Jirí Sgall |
| 2000 | Tilings: Recursivity and Regularity. Julien Cervelle, Bruno Durand |
| 2000 | Tradeoffs between Nondeterminism and Complexity for Communication Protocols and Branching Programs. Juraj Hromkovic, Martin Sauerhoff |
| 2000 | Two-Variable Word Equations. Lucian Ilie, Wojciech Plandowski |
| 2000 | lambda-Coloring of Graphs. Hans L. Bodlaender, Ton Kloks, Richard B. Tan, Jan van Leeuwen |