| 2001 | Approximate distance oracles. | Mikkel Thorup, Uri Zwick |
| 2001 | Fully-dynamic min-cut. | Mikkel Thorup |
| 2001 | Extractor codes. | Amnon Ta-Shma, David Zuckerman |
| 2001 | Loss-less condensers, unbalanced expanders, and extractors. | Amnon Ta-Shma, Christopher Umans, David Zuckerman |
| 2001 | Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. | Daniel A. Spielman, Shang-Hua Teng |
| 2001 | Computing with continuous-time Liapunov systems. | Jir Sma, Pekka Orponen |
| 2001 | Sparse polynomial approximation in finite fields. | Igor E. Shparlinski |
| 2001 | Decidability of string graphs. | Marcus Schaefer, Daniel Stefankovic |
| 2001 | Learning mixtures of arbitrary gaussians. | Sanjeev Arora, Ravi Kannan |
| 2001 | Stackelberg scheduling strategies. | Tim Roughgarden |
| 2001 | Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. | Ran Raz, Amir Shpilka |
| 2001 | Regular resolution lower bounds for the weak pigeonhole principle. | Toniann Pitassi, Ran Raz |
| 2001 | Testing metric properties. | Michal Parnas, Dana Ron |
| 2001 | Algorithms, games, and the internet. | Christos H. Papadimitriou |
| 2001 | On the cell probe complexity of membership and perfect hashing. | Rasmus Pagh |
| 2001 | Anti-presistence: history independent data structures. | Moni Naor, Vanessa Teague |
| 2001 | Communication preserving protocols for secure function evaluation. | Moni Naor, Kobbi Nissim |
| 2001 | On optimal slicing of parallel programs. | Markus Mller-Olm, Helmut Seidl |
| 2001 | Conditions on input vectors for consensus solvability in asynchronous distributed systems. | Achour Mostfaoui, Sergio Rajsbaum, Michel Raynal |
| 2001 | Approximation algorithms for constrained for constrained node weighted steiner tree problems. | Anna Moss, Yuval Rabani |
| 2001 | Edge isoperimetry and rapid mixing on matroids and geometric Markov chains. | Ravi Montenegro, Jung-Bae Son |
| 2001 | Colouring graphs when the number of colours is nearly the maximum degree. | Michael Molloy, Bruce A. Reed |
| 2001 | Profit-earning facility location. | Adam Meyerson |
| 2001 | The price of selfish routing. | Marios Mavronicolas, Paul G. Spirakis |
| 2001 | Explicit lower bound of | Oded Lachish, Ran Raz |