| 2000 | An Improved Lower Bound on the Approximability of Metric TSP and Approximation Algorithms for the TSP with Sharpened Triangle Inequality. | Hans-Joachim Bckenhauer, Juraj Hromkovic, Ralf Klasing, Sebastian Seibert, Walter Unger |
| 2000 | The Stability of Saturated Linear Dynamical Systems Is Undecidable. | Vincent D. Blondel, Olivier Bournez, Pascal Koiran, John N. Tsitsiklis |
| 2000 | Random Generation and Approximate Counting of Ambiguously Described Combinatorial Structures. | Alberto Bertoni, Massimiliano Goldwurm, Massimo Santini |
| 2000 | On the Competitive Ratio of the Work Function Algorithm for the k-Server Problem. | Yair Bartal, Elias Koutsoupias |
| 2000 | An Approximation Algorithm for the Precedence Constrained Scheduling Problem with Hierarchical Communications. | Evripidis Bampis, Rodolphe Giroudeau, Jean-Claude Knig |
| 2000 | Online Dial-a-Ride Problems: Minimizing the Completion Time. | Norbert Ascheuer, Sven Oliver Krumke, Jrg Rambau |
| 2000 | Nondeterministic Instance Complexity and Hard-to-Prove Tautologies. | Vikraman Arvind, Johannes Kbler, Martin Mundhenk, Jacobo Torn |
| 2000 | Graph Isomorphism Is Low for ZPP(NP) and Other Lowness Results. | Vikraman Arvind, Johannes Kbler |
| 2000 | Almost Complete Sets. | Klaus Ambos-Spies, Wolfgang Merkle, Jan Reimann, Sebastiaan Terwijn |
| 2000 | Average-Case Quantum Query Complexity. | Andris Ambainis, Ronald de Wolf |
| 2000 | The Complexity of Planarity Testing. | Eric Allender, Meena Mahajan |
| 2000 | Binary Exponential Backoff Is Stable for High Arrival Rates. | Hesham Al-Ammal, Leslie Ann Goldberg, Philip D. MacKenzie |
| 2000 | On the Two-Variable Fragment of the Equational Theory of the Max-Sum Algebra of the Natural Numbers. | Luca Aceto, Zoltn sik, Anna Inglfsdttir |
| 1999 | Constructing Light Spanning Trees with Small Routing Cost. | Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang |
| 1999 | Classifying Discrete Temporal Properties. | Thomas Wilke |
| 1999 | In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? | Mario Szegedy |
| 1999 | External Selection. | Jop F. Sibeyn |
| 1999 | Universal Distributions and Time-Bounded Kolmogorov Complexity. | Rainer Schuler |
| 1999 | An Optimal Strategy for Searching in Unknown Streets. | Sven Schuierer, Ines Semrau |
| 1999 | Relating Branching Program Size and Formula Size over the Full Binary Basis. | Martin Sauerhoff, Ingo Wegener, Ralph Werchner |
| 1999 | On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions. | Martin Sauerhoff |
| 1999 | On Quadratic Word Equations. | John Michael Robson, Volker Diekert |
| 1999 | Online Matching for Scheduling Problems. | Marco Riedel |
| 1999 | A Complete and Tight Average-Case Analysis of Learning Monomials. | Rdiger Reischuk, Thomas Zeugmann |
| 1999 | Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. | Robert Preis |