| 1999 | Setting Parameters by Example. | David Eppstein |
| 1999 | On Counting Independent Sets in Sparse Graphs. | Martin E. Dyer, Alan M. Frieze, Mark Jerrum |
| 1999 | Magic Functions. | Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer |
| 1999 | Hardness of Approximating the Minimum Distance of a Linear Code. | Ilya Dumer, Daniele Micciancio, Madhu Sudan |
| 1999 | Learning Mixtures of Gaussians. | Sanjoy Dasgupta |
| 1999 | Finding Double Euler Trails of Planar Graphs in Linear Time. | Zhi-Zhong Chen, Xin He, Chun-Hsi Huang |
| 1999 | Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. | Moses Charikar, Sudipto Guha |
| 1999 | Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time. | Timothy M. Chan |
| 1999 | Bounds for Small-Error and Zero-Error Quantum Algorithms. | Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka |
| 1999 | On Universal and Fault-Tolerant Quantum Computing: A Novel Basis and a New Constructive Proof of Universality for Shor's Basis. | P. Oscar Boykin, Tal Mor, Matthew Pulver, Vwani P. Roychowdhury, Farrokh Vatan |
| 1999 | Torpid Mixing of Some Monte Carlo Markov Chain Algorithms in Statistical Physics. | Christian Borgs, Jennifer T. Chayes, Alan M. Frieze, Jeong Han Kim, Prasad Tetali, Eric Vigoda, Van H. Vu |
| 1999 | A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. | Maria Luisa Bonet, Nicola Galesi |
| 1999 | Finely-Competitive Paging. | Avrim Blum, Carl Burch, Adam Kalai |
| 1999 | A 5/2 n | Markus Blser |
| 1999 | Random CNF's are Hard for the Polynomial Calculus. | Eli Ben-Sasson, Russell Impagliazzo |
| 1999 | A Theoretical Framework for Memory-Adaptive Algorithms. | Rakesh D. Barve, Jeffrey Scott Vitter |
| 1999 | An Algorithmic Theory of Learning: Robust Concepts and Random Projection. | Rosa I. Arriaga, Santosh S. Vempala |
| 1999 | Efficient Regular Data Structures and Algorithms for Location and Proximity Problems. | Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet |
| 1999 | A Better Lower Bound for Quantum Algorithms Searching an Ordered List. | Andris Ambainis |
| 1999 | Regular Languages Are Testable with a Constant Number of Queries. | Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy |
| 1999 | Efficient Testing of Large Graphs. | Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy |
| 1999 | A Non-linear Time Lower Bound for Boolean Branching Programs. | Mikls Ajtai |
| 1999 | Primality and Identity Testing via Chinese Remaindering. | Manindra Agrawal, Somenath Biswas |
| 1999 | Approximation Schemes for Minimizing Average Weighted Completion Time with Release Dates. | Foto N. Afrati, Evripidis Bampis, Chandra Chekuri, David R. Karger, Claire Kenyon, Sanjeev Khanna, Ioannis Milis, Maurice Queyranne, Martin Skutella, Clifford Stein, Maxim Sviridenko |
| 1999 | ong-lived Adaptive Collect with Applications. | Yehuda Afek, Gideon Stupp, Dan Touitou |