| 2000 | Entropy Waves, the Zig-Zag Graph Product, and New Constant-Degree Expanders and Extractors. | Omer Reingold, Salil P. Vadhan, Avi Wigderson |
| 2000 | Extracting Randomness via Repeated Condensing. | Omer Reingold, Ronen Shaltiel, Avi Wigderson |
| 2000 | The Quantum Complexity of Set Membership. | Jaikumar Radhakrishnan, Pranab Sen, Srinivasan Venkatesh |
| 2000 | On the Approximability of Trade-offs and Optimal Access of Web Sources. | Christos H. Papadimitriou, Mihalis Yannakakis |
| 2000 | The product replacement algorithm is polynomial. | Igor Pak |
| 2000 | On the boundary complexity of the union of fat triangles. | Jnos Pach, Gbor Tardos |
| 2000 | Polynomial Time Approximation Schemes for Geometric k-Clustering. | Rafail Ostrovsky, Yuval Rabani |
| 2000 | Testing of Functions that have small width Branching Programs. | Ilan Newman |
| 2000 | Cost-Distance: Two Metric Network Design. | Adam Meyerson, Kamesh Munagala, Serge A. Plotkin |
| 2000 | The Online Median Problem. | Ramgopal R. Mettu, C. Greg Plaxton |
| 2000 | Sampling Adsorbing Staircase Walks Using a New Markov Chain Decomposition Method. | Russell A. Martin, Dana Randall |
| 2000 | The Common Fragment of CTL and LTL. | Monika Maidl |
| 2000 | Random graph models for the web graph. | Ravi Kumar, Prabhakar Raghavan, Sridhar Rajagopalan, D. Sivakumar, Andrew Tomkins, Eli Upfal |
| 2000 | Fairness Measures for Resource Allocation. | Amit Kumar, Jon M. Kleinberg |
| 2000 | Detecting a Network Failure. | Jon M. Kleinberg |
| 2000 | Linear Waste of Best Fit Bin Packing on Skewed Distributions. | Claire Kenyon, Michael Mitzenmacher |
| 2000 | Randomized Rumor Spreading. | Richard M. Karp, Christian Schindelhauer, Scott Shenker, Berthold Vcking |
| 2000 | Optimization Problems in Congestion Control. | Richard M. Karp, Elias Koutsoupias, Christos H. Papadimitriou, Scott Shenker |
| 2000 | Building Steiner Trees with Incomplete Global Knowledge. | David R. Karger, Maria Minkoff |
| 2000 | Efficient Algorithms for Universal Portfolios. | Adam Kalai, Santosh S. Vempala |
| 2000 | The Cover Time, the Blanket Time, and the Matthews Bound. | Jeff Kahn, Jeong Han Kim, Lszl Lovsz, Van H. Vu |
| 2000 | Randomizing Polynomials: A New Representation with Applications to Round-Efficient Secure Computation. | Yuval Ishai, Eyal Kushilevitz |
| 2000 | Stable Distributions, Pseudorandom Generators, Embeddings and Data Stream Computation. | Piotr Indyk |
| 2000 | On the Existence of Booster Types. | Maurice Herlihy, Eric Ruppert |
| 2000 | An Improved Quantum Fourier Transform Algorithm and Applications. | Lisa Hales, Sean Hallgren |