| 2001 | Equitable colorings extend Chernoff-Hoeffding bounds. | Sriram V. Pemmaraju |
| 2001 | Randomizing combinatorial algorithms for linear programming when the dimension is moderately high. | Marco Pellegrini |
| 2001 | Game theory, algorithms, and the Internet. | Christos H. Papadimitriou |
| 2001 | Can entropy characterize performance of online algorithms?. | Gopal Pandurangan, Eli Upfal |
| 2001 | Constructing pseudo-random permutations with a prescribed structure. | Moni Naor, Omer Reingold |
| 2001 | Tree packing and approximating k-cuts. | Joseph Naor, Yuval Rabani |
| 2001 | Efficient oblivious transfer protocols. | Moni Naor, Benny Pinkas |
| 2001 | Representing dynamic binary trees succinctly. | J. Ian Munro, Venkatesh Raman, Adam J. Storm |
| 2001 | Sublinear time approximate clustering. | Nina Mishra, Daniel Oblinger, Leonard Pitt |
| 2001 | Fast implementation of depth contours using topological sweep. | Kim Miller, Suneeta Ramaswami, Peter J. Rousseeuw, Joan Antoni Sellars, Diane L. Souvaine, Ileana Streinu, Anja Struyf |
| 2001 | Web caching using access statistics. | Adam Meyerson, Kamesh Munagala, Serge A. Plotkin |
| 2001 | Single-source shortest-paths on arbitrary directed graphs in linear average-case time. | Ulrich Meyer |
| 2001 | External memory BFS on undirected graphs with bounded degree. | Ulrich Meyer |
| 2001 | Fast distributed graph coloring with O(Delta) colors. | Gianluca De Marco, Andrzej Pelc |
| 2001 | Colored Tutte polynomials and Kaufman brackets for graphs of bounded tree width. | Johann A. Makowsky |
| 2001 | I/O-efficient algorithms for graphs of bounded treewidth. | Anil Maheshwari, Norbert Zeh |
| 2001 | The diameter of random massive graphs. | Linyuan Lu |
| 2001 | A new constructive root bound for algebraic expressions. | Chen Li, Chee-Keng Yap |
| 2001 | Generating well-shaped Delaunay meshed in 3D. | Xiang-Yang Li, Shang-Hua Teng |
| 2001 | Gossip is synteny: incomplete gossip and an exact algorithm for syntenic distance. | David Liben-Nowell |
| 2001 | Performance guarentee for online deadline scheduling in the presence of overload. | Tak Wah Lam, Kar-Keung To |
| 2001 | On binary searching with non-uniform costs. | Eduardo Sany Laber, Ruy Luiz Milidi, Artur Alves Pessoa |
| 2001 | On polynomial approximation to the shortest lattice vector length. | Ravi Kumar, D. Sivakumar |
| 2001 | Approximating coloring and maximum independent sets in 3-uniform hypergraphs. | Michael Krivelevich, Ram Nathaniel, Benny Sudakov |
| 2001 | On approximating the achromatic number. | Guy Kortsarz, Robert Krauthgamer |