| 1999 | A Complete and Tight Average-Case Analysis of Learning Monomials. Rüdiger Reischuk, Thomas Zeugmann |
| 1999 | A Logical Characterisation of Linear Time on Nondeterministic Turing Machines. Clemens Lautemann, Nicole Schweikardt, Thomas Schwentick |
| 1999 | A Modal Fixpoint Logic with Chop. Markus Müller-Olm |
| 1999 | A Model of Behaviour Abstraction for Communicating Processes. Maciej Koutny, Giuseppe Pappalardo |
| 1999 | Algorithms for Selfish Agents. Noam Nisan |
| 1999 | An Approximation Algorithm for Max p-Section. Gunnar Andersson |
| 1999 | An Explicit Lower Bound for TSP with Distances One and Two. Lars Engebretsen |
| 1999 | An Optimal Competitive Strategy for Walking in Streets. Christian Icking, Rolf Klein, Elmar Langetepe |
| 1999 | An Optimal Strategy for Searching in Unknown Streets. Sven Schuierer, Ines Semrau |
| 1999 | Approximating Bandwidth by Mixing Layouts of Interval Graphs. Dieter Kratsch, Lorna Stewart |
| 1999 | Balanced Randomized Tree Splitting with Applications to Evolutionary Tree Constructions. Ming-Yang Kao, Andrzej Lingas, Anna Östlin |
| 1999 | Circuit Complexity of Testing Square-Free Numbers. Anna Bernasconi, Igor E. Shparlinski |
| 1999 | Classifying Discrete Temporal Properties. Thomas Wilke |
| 1999 | Completeness of Neighbourhood Logic. Rana Barua, Suman Roy, Zhou Chaochen |
| 1999 | Complexity of Some Problems in Universal Algebra. Clifford Bergman, Giora Slutzki |
| 1999 | Constructing Light Spanning Trees with Small Routing Cost. Bang Ye Wu, Kun-Mao Chao, Chuan Yi Tang |
| 1999 | Costs of General Purpose Learning. John Case, Keh-Jiann Chen, Sanjay Jain |
| 1999 | Decidability and Undecidability of Marked PCP. Vesa Halava, Mika Hirvensalo, Ronald de Wolf |
| 1999 | Descriptive Complexity of Computable Sequences. Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin |
| 1999 | Eliminating Recursion in the µ-Calculus. Martin Otto |
| 1999 | Extending Downward Collapse from 1-versus-2 Queries to j-versus-j+1 Queries. Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
| 1999 | External Selection. Jop F. Sibeyn |
| 1999 | Fast Computations of the Exponential Function. Timm Ahrendt |
| 1999 | Finding Paths with the Right Cost. Matti Nykänen, Esko Ukkonen |
| 1999 | How to Forget a Secret. Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson |
| 1999 | In How Many Steps the k Peg Version of the Towers of Hanoi Game Can Be Solved? Mario Szegedy |
| 1999 | Linear Time 1/2-Approximation Algorithm for Maximum Weighted Matching in General Graphs. Robert Preis |
| 1999 | Lower Bounds for Dynamic Algebraic Problems. Gudmund Skovbjerg Frandsen, Johan P. Hansen, Peter Bro Miltersen |
| 1999 | Memory Organization Schemes for Large Shared Data: A Randomized Solution for Distributed Memory Machines. Alexander E. Andreev, Andrea E. F. Clementi, Paolo Penna, José D. P. Rolim |
| 1999 | Model Checking Lossy Vector Addition Systems. Ahmed Bouajjani, Richard Mayr |
| 1999 | New Branchwidth Territories. Ton Kloks, Jan Kratochvíl, Haiko Müller |
| 1999 | On Optimal Algorithms and Optimal Proof Systems. Jochen Meßner |
| 1999 | On Quadratic Word Equations. John Michael Robson, Volker Diekert |
| 1999 | On Quantum Algorithms for Noncommutative Hidden Subgroups. Mark Ettinger, Peter Høyer |
| 1999 | On the Difference of Horn Theories. Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino |
| 1999 | On the Hardness of Permanent. Jin-Yi Cai, Aduri Pavan, D. Sivakumar |
| 1999 | On the Size of Randomized OBDDs and Read-Once Branching Programs for k-Stable Functions. Martin Sauerhoff |
| 1999 | One-sided Versus Two-sided Error in Probabilistic Computation. Harry Buhrman, Lance Fortnow |
| 1999 | Online Matching for Scheduling Problems. Marco Riedel |
| 1999 | Parallel Searching on m Rays. Mikael Hammar, Bengt J. Nilsson, Sven Schuierer |
| 1999 | Relating Branching Program Size and Formula Size over the Full Binary Basis. Martin Sauerhoff, Ingo Wegener, Ralph Werchner |
| 1999 | STACS 99, 16th Annual Symposium on Theoretical Aspects of Computer Science, Trier, Germany, March 4-6, 1999, Proceedings Christoph Meinel, Sophie Tison |
| 1999 | Scheduling Dynamic Graphs. Andreas Jakoby, Maciej Liskiewicz, Rüdiger Reischuk |
| 1999 | Some Undecidability Results Related to the Star Problem in Trace Monoids. Daniel Kirsten |
| 1999 | Space Bounds for Resolution. Juan Luis Esteban, Jacobo Torán |
| 1999 | Sparse Sets, Approximable Sets, and Parallel Queries to NP. Vikraman Arvind, Jacobo Torán |
| 1999 | Supporting Increment and Decrement Operations in Balancing Networks. William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou |
| 1999 | The Average Time Complexity to Compute Prefix Functions in Processor Networks. Andreas Jakoby |
| 1999 | The Descriptive Complexity Approach to LOGCFL. Clemens Lautemann, Pierre McKenzie, Thomas Schwentick, Heribert Vollmer |
| 1999 | The Reduced Genus of a Multigraph. Patrice Ossona de Mendez |
| 1999 | The Weakness of Self-Complementation. Orna Kupferman, Moshe Y. Vardi |
| 1999 | Treewidth and Minimum Fill-in of Weakly Triangulated Graphs. Vincent Bouchitté, Ioan Todinca |
| 1999 | Universal Distributions and Time-Bounded Kolmogorov Complexity. Rainer Schuler |
| 1999 | Upper Bounds for Vertex Cover Further Improved. Rolf Niedermeier, Peter Rossmanith |
| 1999 | Worst-case Equilibria. Elias Koutsoupias, Christos H. Papadimitriou |