| 2000 | Balanced allocations: the heavily loaded case. | Petra Berenbrink, Artur Czumaj, Angelika Steger, Berthold Vcking |
| 2000 | Tighter bounds for nearest neighbor search and related problems in the cell probe model. | Omer Barkol, Yuval Rabani |
| 2000 | A unified approach to approximating resource allocation and scheduling. | Amotz Bar-Noy, Reuven Bar-Yehuda, Ari Freund, Joseph Naor, Baruch Schieber |
| 2000 | Tight(er) worst-case bounds on dynamic searching and priority queues. | Arne Andersson, Mikkel Thorup |
| 2000 | Computing with highly mixed states (extended abstract). | Andris Ambainis, Leonard J. Schulman, Umesh V. Vazirani |
| 2000 | Quantum lower bounds by quantum arguments. | Andris Ambainis |
| 2000 | Approximation algorithms for geometric shortest path problems. | Lyudmil Aleksandrov, Anil Maheshwari, Jrg-Rdiger Sack |
| 2000 | Space complexity in propositional calculus. | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | A random graph model for massive graphs. | William Aiello, Fan R. K. Chung, Linyuan Lu |
| 2000 | Quantum bit escrow. | Dorit Aharonov, Amnon Ta-Shma, Umesh V. Vazirani, Andrew Chi-Chih Yao |
| 2000 | Compression using efficient multicasting. | Micah Adler, Frank Thomson Leighton |
| 2000 | Setting 2 variables at a time yields a new lower bound for random 3-SAT (extended abstract). | Dimitris Achlioptas |
| 1999 | Outward Rotations: A Tool for Rounding Solutions of Semidefinite Programming Relaxations, with Applications to MAX CUT and Other Problems. | Uri Zwick |
| 1999 | All Pairs Lightest Shortest Paths. | Uri Zwick |
| 1999 | A Polynomial Combinatorial Algorithm for Generalized Minimum Cost Flow. | Kevin D. Wayne |
| 1999 | Robust Logics. | Leslie G. Valiant |
| 1999 | Construction of Extractors Using Pseudo-Random Generators (Extended Abstract). | Luca Trevisan |
| 1999 | Pseudorandom Generators Without the XOR Lemma (Extended Abstract). | Madhu Sudan, Luca Trevisan, Salil P. Vadhan |
| 1999 | A PTAS for Minimizing the Weighted Sum of Job Completion Times on Parallel Machines. | Martin Skutella, Gerhard J. Woeginger |
| 1999 | Computational Sample Complexity and Attribute-Efficient Learning. | Rocco A. Servedio |
| 1999 | Molecular Scale Heat Engines and Scalable Quantum Computation. | Leonard J. Schulman, Umesh V. Vazirani |
| 1999 | Majorizing Estimators and the Approximation of #P-Complete Problems. | Leonard J. Schulman, Vijay V. Vazirani |
| 1999 | From Static to Dynamic Routing: Efficient Transformations of Store-and-Forward Protocols. | Christian Scheideler, Berthold Vcking |
| 1999 | Random Sampling of Large Planar Maps and Convex Polyhedra. | Gilles Schaeffer |
| 1999 | Graph Ramsey Theory and the Polynomial Hierarchy. | Marcus Schaefer |