| 1999 | 40th Annual Symposium on Foundations of Computer Science, FOCS 1999, New York, NY, USA, October 17-18, 1999 |
| 1999 | A 5/2 n Markus Bläser |
| 1999 | A Better Lower Bound for Quantum Algorithms Searching an Ordered List. Andris Ambainis |
| 1999 | A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction. David Peleg, Vitaly Rubinovich |
| 1999 | A Non-linear Time Lower Bound for Boolean Branching Programs. Miklós Ajtai |
| 1999 | A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. Uwe Schöning |
| 1999 | A Study of Proof Search Algorithms for Resolution and Polynomial Calculus. Maria Luisa Bonet, Nicola Galesi |
| 1999 | A Sublinear Time Approximation Scheme for Clustering in Metric Spaces. Piotr Indyk |
| 1999 | A Theoretical Framework for Memory-Adaptive Algorithms. Rakesh D. Barve, Jeffrey Scott Vitter |
| 1999 | Algorithmic Aspects of Protein Structure Similarity. Deborah Goldman, Sorin Istrail, Christos H. Papadimitriou |
| 1999 | All Pairs Shortest Paths in Undirected Graphs with Integer Weights. Avi Shoshan, Uri Zwick |
| 1999 | An Algorithmic Theory of Learning: Robust Concepts and Random Projection. Rosa I. Arriaga, Santosh S. Vempala |
| 1999 | An Approximate L Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan |
| 1999 | Approximate Nearest Neighbor Algorithms for Hausdorff Metrics via Embeddings. Martin Farach-Colton, Piotr Indyk |
| 1999 | Approximating Fractional Multicommodity Flow Independent of the Number of Commodities. Lisa Fleischer |
| 1999 | Approximation Algorithms for Classification Problems with Pairwise Relationships: Metric Labeling and Markov Random Fields. Jon M. Kleinberg, Éva Tardos |
| 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 | Boosting and Hard-Core Sets. Adam R. Klivans, Rocco A. Servedio |
| 1999 | Bounds for Small-Error and Zero-Error Quantum Algorithms. Harry Buhrman, Richard Cleve, Ronald de Wolf, Christof Zalka |
| 1999 | Cache-Oblivious Algorithms. Matteo Frigo, Charles E. Leiserson, Harald Prokop, Sridhar Ramachandran |
| 1999 | Cuts, Trees and l Anupam Gupta, Ilan Newman, Yuri Rabinovich, Alistair Sinclair |
| 1999 | Derandomizing Arthur-Merlin Games Using Hitting Sets. Peter Bro Miltersen, N. V. Vinodchandran |
| 1999 | Dynamic Planar Convex Hull Operations in Near-Logarithmic Amortized Time. Timothy M. Chan |
| 1999 | Edge-Disjoint Routing in Plane Switch Graphs in Linear Time. Karsten Weihe |
| 1999 | Efficient Regular Data Structures and Algorithms for Location and Proximity Problems. Arnon Amir, Alon Efrat, Piotr Indyk, Hanan Samet |
| 1999 | Efficient Testing of Large Graphs. Noga Alon, Eldar Fischer, Michael Krivelevich, Mario Szegedy |
| 1999 | Error Reduction for Extractors. Ran Raz, Omer Reingold, Salil P. Vadhan |
| 1999 | Fairness in Routing and Load Balancing. Jon M. Kleinberg, Yuval Rabani, Éva Tardos |
| 1999 | Finding Double Euler Trails of Planar Graphs in Linear Time. Zhi-Zhong Chen, Xin He, Chun-Hsi Huang |
| 1999 | Finding Maximal Repetitions in a Word in Linear Time. Roman M. Kolpakov, Gregory Kucherov |
| 1999 | Finely-Competitive Paging. Avrim Blum, Carl Burch, Adam Kalai |
| 1999 | Fully Dynamic Algorithms for Maintaining All-Pairs Shortest Paths and Transitive Closure in Digraphs. Valerie King |
| 1999 | Hardness of Approximating Sigma Christopher Umans |
| 1999 | Hardness of Approximating the Minimum Distance of a Linear Code. Ilya Dumer, Daniele Micciancio, Madhu Sudan |
| 1999 | How Asymmetry Helps Load Balancing. Berthold Vöcking |
| 1999 | Improved Bounds for Sampling Colorings. Eric Vigoda |
| 1999 | Improved Combinatorial Algorithms for the Facility Location and k-Median Problems. Moses Charikar, Sudipto Guha |
| 1999 | Learning Mixtures of Gaussians. Sanjoy Dasgupta |
| 1999 | Limits on the Efficiency of One-Way Permutation-Based Hash Functions. Jeong Han Kim, Daniel R. Simon, Prasad Tetali |
| 1999 | Lovász's Lemma for the Three-Dimensional K-Level of Concave Surfaces and its Applications. Naoki Katoh, Takeshi Tokuyama |
| 1999 | Magic Functions. Cynthia Dwork, Moni Naor, Omer Reingold, Larry J. Stockmeyer |
| 1999 | Markovian Coupling vs. Conductance for the Jerrum-Sinclair Chain. V. S. Anil Kumar, H. Ramesh |
| 1999 | Near-Optimal Conversion of Hardness into Pseudo-Randomness. Russell Impagliazzo, Ronen Shaltiel, Avi Wigderson |
| 1999 | Non-Interactive CryptoComputing For NC Tomas Sander, Adam L. Young, Moti Yung |
| 1999 | Non-Malleable Non-Interactive Zero Knowledge and Adaptive Chosen-Ciphertext Security. Amit Sahai |
| 1999 | Noncryptographic Selection Protocols. Uriel Feige |
| 1999 | On Counting Independent Sets in Sparse Graphs. Martin E. Dyer, Alan M. Frieze, Mark Jerrum |
| 1999 | On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. John Watrous |
| 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 | On the Complexity of SAT. Richard J. Lipton, Anastasios Viglas |
| 1999 | Online Scheduling to Minimize Average Stretch. S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke |
| 1999 | Optimal Lower Bounds for Quantum Automata and Random Access Codes. Ashwin Nayak |
| 1999 | PSPACE Has Constant-Round Quantum Interactive Proof Systems. John Watrous |
| 1999 | Primal-Dual Approximation Algorithms for Metric Facility Location and k-Median Problems. Kamal Jain, Vijay V. Vazirani |
| 1999 | Primality and Identity Testing via Chinese Remaindering. Manindra Agrawal, Somenath Biswas |
| 1999 | Random CNF's are Hard for the Polynomial Calculus. Eli Ben-Sasson, Russell Impagliazzo |
| 1999 | Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. Ben Morris, Alistair Sinclair |
| 1999 | Reducing Network Congestion and Blocking Probability Through Balanced Allocation. Malwina J. Luczak, Eli Upfal |
| 1999 | Regular Languages Are Testable with a Constant Number of Queries. Noga Alon, Michael Krivelevich, Ilan Newman, Mario Szegedy |
| 1999 | Satisfiability of Word Equations with Constants is in PSPACE. Wojciech Plandowski |
| 1999 | Setting Parameters by Example. David Eppstein |
| 1999 | Stochastic Load Balancing and Related Problems. Ashish Goel, Piotr Indyk |
| 1999 | Taking a Walk in a Planar Arrangement. Sariel Har-Peled |
| 1999 | The Directed Steiner Network Problem is Tractable for a Constant Number of Terminals. Jon Feldman, Matthias Ruhl |
| 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 | Verifiable Random Functions. Silvio Micali, Michael O. Rabin, Salil P. Vadhan |
| 1999 | Weak Adversaries for the k-Server Problem. Elias Koutsoupias |
| 1999 | ong-lived Adaptive Collect with Applications. Yehuda Afek, Gideon Stupp, Dan Touitou |