| 1999 | Lower Bounds for Leader Election and Collective Coin-Flipping in the Perfect Information Model. | Alexander Russell, Michael E. Saks, David Zuckerman |
| 1999 | On the Complexity of Diophantine Geometry in Low Dimensions (Extended Abstract). | J. Maurice Rojas |
| 1999 | Extracting all the Randomness and Reducing the Error in Trevisan's Extractors. | Ran Raz, Omer Reingold, Salil P. Vadhan |
| 1999 | On Recycling the Randomness of States in Space Bounded Computation. | Ran Raz, Omer Reingold |
| 1999 | Exponential Separation of Quantum and Classical Communication Complexity. | Ran Raz |
| 1999 | The Communication Complexity of Pointer Chasing: Applications of Entropy and Sampling. | Stephen Ponzio, Jaikumar Radhakrishnan, Srinivasan Venkatesh |
| 1999 | Satisfiability of Word Equations with Constants is in NEXPTIME. | Wojciech Plandowski |
| 1999 | Static and Dynamic Evaluation of QoS Properties. | Gopal Pandurangan, Eli Upfal |
| 1999 | The Complexity of the Matrix Eigenproblem. | Victor Y. Pan, Zhao Q. Chen |
| 1999 | A Displacement Approach to Efficient Decoding of Algebraic-Geometric Codes. | Vadim Olshevsky, Mohammad Amin Shokrollahi |
| 1999 | Algorithmic Mechanism Design (Extended Abstract). | Noam Nisan, Amir Ronen |
| 1999 | The Quantum Query Complexity of Approximating the Median and Related Statistics. | Ashwin Nayak, Felix Wu |
| 1999 | Oblivious Transfer and Polynomial Evaluation. | Moni Naor, Benny Pinkas |
| 1999 | Compact Grid Layouts of Multi-Level Networks. | S. Muthukrishnan, Mike Paterson, Sleyman Cenk Sahinalp, Torsten Suel |
| 1999 | Hypergraph Isomorphism and Structural Equivalence of Boolean Functions. | Eugene M. Luks |
| 1999 | Faster Mixing via Average Conductance. | Lszl Lovsz, Ravi Kannan |
| 1999 | Finding Similar Regions in Many Strings. | Ming Li, Bin Ma, Lusheng Wang |
| 1999 | Covering Rectilinear Polygons with Axis-Parallel Rectangles. | V. S. Anil Kumar, H. Ramesh |
| 1999 | Graph Nonisomorphism has Subexponential Size Proofs Unless the Polynomial-Time Hierarchy Collapses. | Adam R. Klivans, Dieter van Melkebeek |
| 1999 | Approximate Testing with Relative Error. | Marcos A. Kiwi, Frdric Magniez, Miklos Santha |
| 1999 | A Fully Dynamic Algorithm for Maintaining the Transitive Closure. | Valerie King, Garry Sagert |
| 1999 | Rounding Algorithms for a Geometric Embedding of Minimum Multiway Cut. | David R. Karger, Philip N. Klein, Clifford Stein, Mikkel Thorup, Neal E. Young |
| 1999 | Efficient Computation of Geodesic Shortest Paths. | Sanjiv Kapoor |
| 1999 | Makespan Minimization in Job Shops: A Polynomial Time Approximation Scheme. | Klaus Jansen, Roberto Solis-Oba, Maxim Sviridenko |
| 1999 | Improved Approximation Schemes for Scheduling Unrelated Parallel Machines. | Klaus Jansen, Lorant Porkolab |