| 2001 | Biased dictionaries with fast insert/deletes. | Funda Ergn, Sleyman Cenk Sahinalp, Jonathan Sharp, Rakesh K. Sinha |
| 2001 | (1+epsilon, beta)-spanner constructions for general graphs. | Michael Elkin, David Peleg |
| 2001 | Excellent codes from modular curves. | Noam D. Elkies |
| 2001 | Complex tilings. | Bruno Durand, Leonid A. Levin, Alexander Shen |
| 2001 | Optimal outlier removal in high-dimensional. | John Dunagan, Santosh S. Vempala |
| 2001 | Algorithms for minimizing weighted flow time. | Chandra Chekuri, Sanjeev Khanna, An Zhu |
| 2001 | Lower bounds for intersection searching and fractional cascading in higher dimension. | Bernard Chazelle, Ding Liu |
| 2001 | Clustering to minimize the sum of cluster diameters. | Moses Charikar, Rina Panigrahy |
| 2001 | Black-box concurrent zero-knowledge requires Omega~(log n) rounds. | Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen |
| 2001 | The complexity of maximal constraint languages. | Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |
| 2001 | Sharp threshold and scaling window for the integer partitioning problem. | Christian Borgs, Jennifer T. Chayes, Boris G. Pittel |
| 2001 | A read-once branching program lower bound of Omega(2 | Beate Bollig, Philipp Woelfel |
| 2001 | Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. | Luca Becchetti, Stefano Leonardi |
| 2001 | Approximating min-sum | Yair Bartal, Moses Charikar, Danny Raz |
| 2001 | Sampling algorithms: lower bounds and applications. | Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar |
| 2001 | Spectral analysis of data. | Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, Jared Saia |
| 2001 | Local search heuristic for k-median and facility location problems. | Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit |
| 2001 | The complexity of analytic tableaux. | Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart |
| 2001 | Quantum walks on graphs. | Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani |
| 2001 | One-dimensional quantum walks. | Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous |
| 2001 | A new protocol and lower bounds for quantum coin flipping. | Andris Ambainis |
| 2001 | Optimal static range reporting in one dimension. | Stephen Alstrup, Gerth Stlting Brodal, Theis Rauhe |
| 2001 | Quantitative solution of omega-regular games. | Luca de Alfaro, Rupak Majumdar |
| 2001 | A sieve algorithm for the shortest lattice vector problem. | Mikls Ajtai, Ravi Kumar, D. Sivakumar |
| 2001 | Running time and program size for self-assembled squares. | Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang |