| 2001 | Euler paths in series parallel graphs. | S. Rao Kosaraju |
| 2001 | Learning DNF in time 2 | Adam R. Klivans, Rocco A. Servedio |
| 2001 | Randomness efficient identity testing of multivariate polynomials. | Adam R. Klivans, Daniel A. Spielman |
| 2001 | Interaction in quantum communication and the complexity of set disjointness. | Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman |
| 2001 | Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. | Joe Kilian, Erez Petrank |
| 2001 | Buffer overflow management in QoS switches. | Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko |
| 2001 | Spatial gossip and resource location protocols. | David Kempe, Jon M. Kleinberg, Alan J. Demers |
| 2001 | Dynamic TCP acknowledgement and other stories about e/(e-1). | Anna R. Karlin, Claire Kenyon, Dana Randall |
| 2001 | A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. | Mark Jerrum, Alistair Sinclair, Eric Vigoda |
| 2001 | Online server allocation in a server farm via benefit task systems. | T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko |
| 2001 | Applications of approximation algorithms to cooperative games. | Kamal Jain, Vijay V. Vazirani |
| 2001 | A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D. | Christian Icking, Lihong Ma |
| 2001 | Private approximation of NP-hard functions. | Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim |
| 2001 | Provisioning a virtual private network: a network design problem for multicommodity flow. | Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, Blent Yener |
| 2001 | A constant factor approximation for the single sink edge installation problems. | Sudipto Guha, Adam Meyerson, Kamesh Munagala |
| 2001 | Data-streams and histograms. | Sudipto Guha, Nick Koudas, Kyuseok Shim |
| 2001 | When is the evaluation of conjunctive queries tractable? | Martin Grohe, Thomas Schwentick, Luc Segoufin |
| 2001 | Computing crossing numbers in quadratic time. | Martin Grohe |
| 2001 | Quantum mechanical algorithms for the nonabelian hidden subgroup problem. | Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani |
| 2001 | Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. | Michel X. Goemans, David P. Williamson |
| 2001 | The round complexity of verifiable secret sharing and secure multicast. | Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin |
| 2001 | One line and n points. | Bernd Grtner, Jzsef Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr |
| 2001 | Compatible sequences and a slow Winkler percolation. | Pter Gcs |
| 2001 | Testing of matrix properties. | Eldar Fischer, Ilan Newman |
| 2001 | On the integrality ratio of semidefinite relaxations of MAX CUT. | Uriel Feige, Gideon Schechtman |