| 2001 | Counting Axioms Do Not Polynomially Simulate Counting Gates. | Russell Impagliazzo, Nathan Segerlind |
| 2001 | Vickrey Prices and Shortest Paths: What is an Edge Worth?. | John Hershberger, Subhash Suri |
| 2001 | Query Efficient PCPs with Perfect Completeness. | Johan Hstad, Subhash Khot |
| 2001 | Approximate Shape Fitting via Linearization. | Sariel Har-Peled, Kasturi R. Varadarajan |
| 2001 | A Replacement for Voronoi Diagrams of Near Linear Size. | Sariel Har-Peled |
| 2001 | Clustering Motion. | Sariel Har-Peled |
| 2001 | Expander-Based Constructions of Efficiently Decodable Codes. | Venkatesan Guruswami, Piotr Indyk |
| 2001 | Traveling with a Pez Dispenser (Or, Routing Issues in MPLS). | Anupam Gupta, Amit Kumar, Rajeev Rastogi |
| 2001 | Sorting and Selection with Structured Costs. | Anupam Gupta, Amit Kumar |
| 2001 | Three Theorems Regarding Testing Graph Properties. | Oded Goldreich, Luca Trevisan |
| 2001 | On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates. | Yael Gertner, Tal Malkin, Omer Reingold |
| 2001 | An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. | Lisa Fleischer, Kamal Jain, David P. Williamson |
| 2001 | Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time. | Jittat Fakcharoenphol, Satish Rao |
| 2001 | Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. | Martin E. Dyer, Alan M. Frieze |
| 2001 | Fast Monte-Carlo Algorithms for Approximate Matrix Multiplication. | Petros Drineas, Ravi Kannan |
| 2001 | Fully Dynamic All Pairs Shortest Paths with Real Edge Weights. | Camil Demetrescu, Giuseppe F. Italiano |
| 2001 | "Planar" Tautologies Hard for Resolution. | Stefan S. Dantchev, Sren Riis |
| 2001 | How Powerful is Adiabatic Quantum Computation?. | Wim van Dam, Michele Mosca, Umesh V. Vazirani |
| 2001 | The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time. | Hubert Comon, Guillem Godoy, Robert Nieuwenhuis |
| 2001 | Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. | Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani |
| 2001 | Approximating Directed Multicuts. | Joseph Cheriyan, Howard J. Karloff, Yuval Rabani |
| 2001 | Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. | Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao |
| 2001 | Universally Composable Security: A New Paradigm for Cryptographic Protocols. | Ran Canetti |
| 2001 | S | Jin-yi Cai |
| 2001 | On the Average-Case Hardness of CVP. | Jin-yi Cai |