| 1999 | Eliminating Recursion in the µ-Calculus. | Martin Otto |
| 1999 | Finding Paths with the Right Cost. | Matti Nyknen, Esko Ukkonen |
| 1999 | Algorithms for Selfish Agents. | Noam Nisan |
| 1999 | Upper Bounds for Vertex Cover Further Improved. | Rolf Niedermeier, Peter Rossmanith |
| 1999 | A Modal Fixpoint Logic with Chop. | Markus Mller-Olm |
| 1999 | On Optimal Algorithms and Optimal Proof Systems. | Jochen Mener |
| 1999 | The Reduced Genus of a Multigraph. | Patrice Ossona de Mendez |
| 1999 | A Logical Characterisation of Linear Time on Nondeterministic Turing Machines. | Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick |
| 1999 | The Descriptive Complexity Approach to LOGCFL. | Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer |
| 1999 | The Weakness of Self-Complementation. | Orna Kupferman, Moshe Y. Vardi |
| 1999 | Approximating Bandwidth by Mixing Layouts of Interval Graphs. | Dieter Kratsch, Lorna Stewart |
| 1999 | Worst-case Equilibria. | Elias Koutsoupias, Christos H. Papadimitriou |
| 1999 | A Model of Behaviour Abstraction for Communicating Processes. | Maciej Koutny, Giuseppe Pappalardo |
| 1999 | New Branchwidth Territories. | Ton Kloks, Jan Kratochvl, Haiko Mller |
| 1999 | Some Undecidability Results Related to the Star Problem in Trace Monoids. | Daniel Kirsten |
| 1999 | Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions. | Ming-Yang Kao, Andrzej Lingas, Anna stlin |
| 1999 | Scheduling Dynamic Graphs. | Andreas Jakoby, Maciej Liskiewicz, Rdiger Reischuk |
| 1999 | The Average Time Complexity to Compute Prefix Functions in Processor Networks. | Andreas Jakoby |
| 1999 | An Optimal Competitive Strategy for Walking in Streets. | Christian Icking, Rolf Klein, Elmar Langetepe |
| 1999 | Decidability and Undecidability of Marked PCP. | Vesa Halava, Mika Hirvensalo, Ronald de Wolf |
| 1999 | Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries. | Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
| 1999 | Parallel Searching on m Rays. | Mikael Hammar, Bengt J. Nilsson, Sven Schuierer |
| 1999 | Lower Bounds for Dynamic Algebraic Problems. | Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen |
| 1999 | On Quantum Algorithms for Noncommutative Hidden Subgroups. | Mark Ettinger, Peter Hyer |
| 1999 | Space Bounds for Resolution. | Juan Luis Esteban, Jacobo Torn |