| 1999 | New Upper Bounds for MaxSat. | Rolf Niedermeier, Peter Rossmanith |
| 1999 | Leader Election by d Dimensional Cellular Automata. | Codrin M. Nichitiu, Eric Rmila |
| 1999 | Formalizing a Lazy Substitution Proof System for µ-calculus in the Calculus of Inductive Constructions. | Marino Miculan |
| 1999 | Efficient Merging, Construction, and Maintenance of Evolutionary Trees. | Andrzej Lingas, Hans Olsson, Anna stlin |
| 1999 | Relations between Local and Global Periodicity of Words. | Arto Lepist |
| 1999 | Shortest Anisotropic Paths on Terrains. | Mark Lanthier, Anil Maheshwari, Jrg-Rdiger Sack |
| 1999 | Solos in Concert. | Cosimo Laneve, Bjrn Victor |
| 1999 | Simulation Preorder on Simple Process Algebras. | Antonn Kucera, Richard Mayr |
| 1999 | Approximations by OBDDs and the Variable Ordering Problem. | Matthias Krause, Petr Savick, Ingo Wegener |
| 1999 | Two Techniques in the Area of the Star Problem. | Daniel Kirsten, Jerzy Marcinkowski |
| 1999 | A Connection between the Star Problem and the Finite Power Property in Trace Monoids. | Daniel Kirsten |
| 1999 | Linear-Time Construction of Two-Dimensional Suffix Trees. | Dong Kyue Kim, Kunsoo Park |
| 1999 | Average-Case Complexity of Shellsort. | Tao Jiang, Ming Li, Paul M. B. Vitnyi |
| 1999 | Stable Marriage with Incomplete Lists and Ties. | Kazuo Iwama, David F. Manlove, Shuichi Miyazaki, Yasufumi Morita |
| 1999 | On the Power of Las Vegas II. Two-Way Finite Automata. | Juraj Hromkovic, Georg Schnitger |
| 1999 | A Framework for Decidable Metrical Logics. | Yoram Hirshfeld, Alexander Moshe Rabinovich |
| 1999 | Bisimulation Equivanlence Is Decidable for Normed Process Algebra. | Yoram Hirshfeld, Mark Jerrum |
| 1999 | Distributed Probabilistic Polling and Applications to Proportionate Agreement. | Yehuda Hassin, David Peleg |
| 1999 | Observations about the Nature and State of Computer Science (Keynote Address). | Juris Hartmanis |
| 1999 | Approximation Results for Kinetic Variants of TSP. | Mikael Hammar, Bengt J. Nilsson |
| 1999 | On the Complements of Partial k-Trees. | Arvind Gupta, Damon Kaller, Thomas C. Shermer |
| 1999 | Efficient Techniques for Maintaining Multidimensional Keys in Linked Data Structures. | Roberto Grossi, Giuseppe F. Italiano |
| 1999 | Computing LOGCFL Certificates. | Georg Gottlob, Nicola Leone, Francesco Scarcello |
| 1999 | Compact Routing Tables for Graphs of Bounded Genus. | Cyril Gavoille, Nicolas Hanusse |
| 1999 | Comparison of Process Algebra Equivalences Using Formats. | Vashti Galpin |