| 2001 | The Complexity of Factors of Multivariate Polynomials. | Peter Brgisser |
| 2001 | Arc-Disjoint Paths in Expander Digraphs. | Tom Bohman, Alan M. Frieze |
| 2001 | The Natural Work-Stealing Algorithm is Stable. | Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg |
| 2001 | Testing Random Variables for Independence and Identity. | Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White |
| 2001 | A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems. | Yair Bartal, Bla Bollobs, Manor Mendel |
| 2001 | Resettably-Sound Zero-Knowledge and its Applications. | Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell |
| 2001 | How to Go Beyond the Black-Box Simulation Barrier. | Boaz Barak |
| 2001 | Simple Routing Strategies for Adversarial Systems. | Baruch Awerbuch, Petra Berenbrink, Andr Brinkmann, Christian Scheideler |
| 2001 | Truthful Mechanisms for One-Parameter Agents. | Aaron Archer, va Tardos |
| 2001 | Source Routing and Scheduling in Packet Networks. | Matthew Andrews, Antonio Fernndez, Ashish Goel, Lisa Zhang |
| 2001 | Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. | Noga Alon, Alexander Lubotzky, Avi Wigderson |
| 2001 | Testing Subgraphs in Large Graphs. | Noga Alon |
| 2001 | Resolution is Not Automatizable Unless W[P] is Tractable. | Michael Alekhnovich, Alexander A. Razborov |
| 2001 | Lower Bounds for Polynomial Calculus: Non-Binomial Case. | Michael Alekhnovich, Alexander A. Razborov |
| 2001 | Random Evolution in Massive Graphs. | William Aiello, Fan R. K. Chung, Linyuan Lu |
| 2001 | On the Complexity of Many Faces in Arrangements of Circles. | Pankaj K. Agarwal, Boris Aronov, Micha Sharir |
| 2001 | Web Search via Hub Synthesis. | Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry |
| 2000 | Succinct quantum proofs for properties of finite groups. | John Watrous |
| 2000 | On Clusterings - Good, Bad and Spectral. | Ravi Kannan, Santosh S. Vempala, Adrian Vetta |
| 2000 | Extracting Randomness from Samplable Distributions. | Luca Trevisan, Salil P. Vadhan |
| 2000 | On the Hardness of Graph Isomorphism. | Jacobo Torn |
| 2000 | Approximability and in-approximability results for no-wait shop scheduling. | Maxim Sviridenko, Gerhard J. Woeginger |
| 2000 | A Combinatorial Approach to Planar Non-colliding Robot Arm Motion Planning. | Ileana Streinu |
| 2000 | Approximating the single source unsplittable min-cost flow problem. | Martin Skutella |
| 2000 | How Bad is Selfish Routing? | Tim Roughgarden, va Tardos |