| 1999 | Improved Upper Bounds on Information-Theoretic Private Information Retrieval (Extended Abstract). | Yuval Ishai, Eyal Kushilevitz |
| 1999 | Inerpolation of Symmetric Functions and a New Type of Combinatorial Design. | Piotr Indyk |
| 1999 | Sublinear Time Algorithms for Metric Space Problems. | Piotr Indyk |
| 1999 | Quantum Fourier Sampling Simplified. | Lisa Hales, Sean Hallgren |
| 1999 | Near-Optimal Hardness Results and Approximation Algorithms for Edge-Disjoint Paths and Related Problems. | Venkatesan Guruswami, Sanjeev Khanna, Rajmohan Rajaraman, F. Bruce Shepherd, Mihalis Yannakakis |
| 1999 | Embedding Tree Metrics Into Low Dimensional Euclidean Spaces. | Anupam Gupta |
| 1999 | Efficient Recovery from Power Outage (Extended Abstract). | Sudipto Guha, Anna Moss, Joseph Naor, Baruch Schieber |
| 1999 | Chinese Remaindering with Errors. | Oded Goldreich, Dana Ron, Madhu Sudan |
| 1999 | Scheduling Data Transfers in a Network and the Set Scheduling Problem. | Ashish Goel, Monika Rauch Henzinger, Serge A. Plotkin, va Tardos |
| 1999 | Stability of Adaptive and Non-Adaptive Packet Routing Policies in Adversarial Queueing Networks. | David Gamarnik |
| 1999 | A Theorem on Sensitivity and Applications in Private Computation. | Anna Gl, Adi Rosn |
| 1999 | Unique Maximum Matching Algorithms. | Harold N. Gabow, Haim Kaplan, Robert Endre Tarjan |
| 1999 | Multi-Method Dispatching: A Geometric Approach With Applications to String Matching Problems. | Paolo Ferragina, S. Muthukrishnan, Mark de Berg |
| 1999 | Nonmonotonic Phenomena in Packet Routing. | Uriel Feige |
| 1999 | Complexity of Graph Partition Problems. | Toms Feder, Pavol Hell, Sulamita Klein, Rajeev Motwani |
| 1999 | Fast Approximate PCPs. | Funda Ergn, Ravi Kumar, Ronitt Rubinfeld |
| 1999 | Scheduling in the Dark. | Jeff Edmonds |
| 1999 | Design Networks with Bounded Pairwise Distance. | Yevgeniy Dodis, Sanjeev Khanna |
| 1999 | PCP Characterizations of NP: Towards a Polynomially-Small Error-Probability. | Irit Dinur, Eldar Fischer, Guy Kindler, Ran Raz, Shmuel Safra |
| 1999 | Bit Complexity of Breaking and Achieving Symmetry in Chains and Rings (Extended Abstract). | Yefim Dinitz, Shlomo Moran, Sergio Rajsbaum |
| 1999 | Security-Preserving Hardness-Amplification for Any Regular One-Way Function. | Giovanni Di Crescenzo, Russell Impagliazzo |
| 1999 | Connection Caching. | Edith Cohen, Haim Kaplan, Uri Zwick |
| 1999 | Exploiting Regularities in Web Traffic Patterns for Cache Replacement. | Edith Cohen, Haim Kaplan |
| 1999 | A Polynomial Time Approximation Scheme for General Multiprocessor Job Scheduling (Extended Abstract). | Jianer Chen, Antonio Miranda |
| 1999 | Lifting Markov Chains to Speed up Mixing. | Fang Chen, Lszl Lovsz, Igor Pak |