| 1999 | Verifiable Random Functions. | Silvio Micali, Michael O. Rabin, Salil P. Vadhan |
| 1999 | Reducing Network Congestion and Blocking Probability Through Balanced Allocation. | Malwina J. Luczak, Eli Upfal |
| 1999 | On the Complexity of SAT. | Richard J. Lipton, Anastasios Viglas |
| 1999 | Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain. | V. S. Anil Kumar, H. Ramesh |
| 1999 | Weak Adversaries for the k-Server Problem. | Elias Koutsoupias |
| 1999 | Finding Maximal Repetitions in a Word in Linear Time. | Roman M. Kolpakov, Gregory Kucherov |
| 1999 | Boosting and Hard-Core Sets. | Adam R. Klivans, Rocco A. Servedio |
| 1999 | Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. | Jon M. Kleinberg, va Tardos |
| 1999 | Fairness in Routing and Load Balancing. | Jon M. Kleinberg, Yuval Rabani, va Tardos |
| 1999 | Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. | Valerie King |
| 1999 | Limits on the Efficiency of One-Way Permutation-Based Hash Functions. | Jeong Han Kim, Daniel R. Simon, Prasad Tetali |
| 1999 | Lovsz's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications. | Naoki Katoh, Takeshi Tokuyama |
| 1999 | Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. | Kamal Jain, Vijay V. Vazirani |
| 1999 | A Sublinear Time Approximation Scheme for Clustering in Metric Spaces. | Piotr Indyk |
| 1999 | Near-Optimal Conversion of Hardness into Pseudo-Randomness. | Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
| 1999 | Taking a Walk in a Planar Arrangement. | Sariel Har-Peled |
| 1999 | Cuts, Trees and l | Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
| 1999 | Algorithmic Aspects of Protein Structure Similarity. | Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou |
| 1999 | Stochastic Load Balancing and Related Problems. | Ashish Goel, Piotr Indyk |
| 1999 | Cache-Oblivious Algorithms. | Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran |
| 1999 | Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. | Lisa Fleischer |
| 1999 | The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. | Jon Feldman, Matthias Ruhl |
| 1999 | An Approximate L | Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan |
| 1999 | Noncryptographic Selection Protocols. | Uriel Feige |
| 1999 | Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. | Martin Farach-Colton, Piotr Indyk |