| 2000 | Using Upper Confidence Bounds for Online Learning. | Peter Auer |
| 2000 | Nearly Optimal Expected-Case Planar Point Location. | Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2000 | Private Quantum Channels. | Andris Ambainis, Michele Mosca, Alain Tapp, Ronald de Wolf |
| 2000 | New Data Structures for Orthogonal Range Searching. | Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe |
| 2000 | Testing of Clustering. | Noga Alon, Seannie Dar, Michal Parnas, Dana Ron |
| 2000 | Universality and Tolerance. | Noga Alon, Michael R. Capalbo, Yoshiharu Kohayakawa, Vojtech Rdl, Andrzej Rucinski, Endre Szemerdi |
| 2000 | Pseudorandom Generators in Propositional Proof Complexity. | Michael Alekhnovich, Eli Ben-Sasson, Alexander A. Razborov, Avi Wigderson |
| 2000 | Optimal myopic algorithms for random 3-SAT. | Dimitris Achlioptas, Gregory B. Sorkin |
| 1999 | Edge-Disjoint Routing in Plane Switch Graphs in Linear Time. | Karsten Weihe |
| 1999 | On Quantum and Classical Space-bounded Processes with Algebraic Transition Amplitudes. | John Watrous |
| 1999 | PSPACE Has Constant-Round Quantum Interactive Proof Systems. | John Watrous |
| 1999 | How Asymmetry Helps Load Balancing. | Berthold Vcking |
| 1999 | Improved Bounds for Sampling Colorings. | Eric Vigoda |
| 1999 | Hardness of Approximating Sigma | Christopher Umans |
| 1999 | All Pairs Shortest Paths in Undirected Graphs with Integer Weights. | Avi Shoshan, Uri Zwick |
| 1999 | A Probabilistic Algorithm for k-SAT and Constraint Satisfaction Problems. | Uwe Schning |
| 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 | Error Reduction for Extractors. | Ran Raz, Omer Reingold, Salil P. Vadhan |
| 1999 | Satisfiability of Word Equations with Constants is in PSPACE. | Wojciech Plandowski |
| 1999 | A Near-Tight Lower Bound on the Time Complexity of Distributed MST Construction. | David Peleg, Vitaly Rubinovich |
| 1999 | Optimal Lower Bounds for Quantum Automata and Random Access Codes. | Ashwin Nayak |
| 1999 | Online Scheduling to Minimize Average Stretch. | S. Muthukrishnan, Rajmohan Rajaraman, Anthony Shaheen, Johannes Gehrke |
| 1999 | Random Walks on Truncated Cubes and Sampling 0-1 Knapsack Solutions. | Ben Morris, Alistair Sinclair |
| 1999 | Derandomizing Arthur-Merlin Games Using Hitting Sets. | Peter Bro Miltersen, N. V. Vinodchandran |