| 1999 | An Explicit Lower Bound for TSP with Distances One and Two. | Lars Engebretsen |
| 1999 | On the Difference of Horn Theories. | Thomas Eiter, Toshihide Ibaraki, Kazuhisa Makino |
| 1999 | Descriptive Complexity of Computable Sequences. | Bruno Durand, Alexander Shen, Nikolai K. Vereshchagin |
| 1999 | How to Forget a Secret. | Giovanni Di Crescenzo, Niels Ferguson, Russell Impagliazzo, Markus Jakobsson |
| 1999 | Costs of General Purpose Learning. | John Case, Keh-Jiann Chen, Sanjay Jain |
| 1999 | On the Hardness of Permanent. | Jin-yi Cai, Aduri Pavan, D. Sivakumar |
| 1999 | One-sided Versus Two-sided Error in Probabilistic Computation. | Harry Buhrman, Lance Fortnow |
| 1999 | Treewidth and Minimum Fill-in of Weakly Triangulated Graphs. | Vincent Bouchitt, Ioan Todinca |
| 1999 | Model Checking Lossy Vector Addition Systems. | Ahmed Bouajjani, Richard Mayr |
| 1999 | Circuit Complexity of Testing Square-Free Numbers. | Anna Bernasconi, Igor E. Shparlinski |
| 1999 | Complexity of Some Problems in Universal Algebra. | Clifford Bergman, Giora Slutzki |
| 1999 | Completeness of Neighbourhood Logic. | Rana Barua, Suman Roy, Zhou Chaochen |
| 1999 | Sparse Sets, Approximable Sets, and Parallel Queries to NP. | Vikraman Arvind, Jacobo Torn |
| 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 | An Approximation Algorithm for Max p-Section. | Gunnar Andersson |
| 1999 | Supporting Increment and Decrement Operations in Balancing Networks. | William Aiello, Costas Busch, Maurice Herlihy, Marios Mavronicolas, Nir Shavit, Dan Touitou |
| 1999 | Fast Computations of the Exponential Function. | Timm Ahrendt |
| 1998 | Provable Security for Block Ciphers by Decorrelation. | Serge Vaudenay |
| 1998 | Floats, Integers, and Single Source Shortest Paths. | Mikkel Thorup |
| 1998 | Languages Defined With Modular Counting Quantifiers (Extended Abstract). | Howard Straubing |
| 1998 | Random Sparse Bit Strings at the Threshold of Adjacency. | Joel Spencer, Katherine St. John |
| 1998 | On the Existence of Polynomial Time Approximation Schemes for OBDD Minimization (Extended Abstract). | Detlef Sieling |
| 1998 | The (Parallel) Approximability of Non-Boolean Satisfiability Problems and Restricted Integer Programming. | Maria J. Serna, Luca Trevisan, Fatos Xhafa |
| 1998 | Local Normal Forms for First-Order Logic with Applications to Games and Automata. | Thomas Schwentick, Klaus Barthelmann |
| 1998 | Lower Bounds for Randomized Read-k-Times Branching Programs (Extended Abstract). | Martin Sauerhoff |