| 2001 | "Planar" Tautologies Hard for Resolution. Stefan S. Dantchev, Søren Riis |
| 2001 | 42nd Annual Symposium on Foundations of Computer Science, FOCS 2001, Las Vegas, Nevada, USA, October 14-17, 2001 |
| 2001 | A Ramsy-type Theorem for Metric Spaces and its Applications for Metrical Task Systems and Related Problems. Yair Bartal, Béla Bollobás, Manor Mendel |
| 2001 | A Replacement for Voronoi Diagrams of Near Linear Size. Sariel Har-Peled |
| 2001 | Algorithmic Applications of Low-Distortion Geometric Embeddings. Piotr Indyk |
| 2001 | Almost Tight Upper Bounds for Vertical Decompositions in Four Dimensions. Vladlen Koltun |
| 2001 | An Iterative Rounding 2-Approximation Algorithm for the Element Connectivity Problem. Lisa Fleischer, Kamal Jain, David P. Williamson |
| 2001 | Approximate Shape Fitting via Linearization. Sariel Har-Peled, Kasturi R. Varadarajan |
| 2001 | Approximating Directed Multicuts. Joseph Cheriyan, Howard J. Karloff, Yuval Rabani |
| 2001 | Approximation Algorithms for the Job Interval Selection Problem and Related Scheduling Problems. Julia Chuzhoy, Rafail Ostrovsky, Yuval Rabani |
| 2001 | Arc-Disjoint Paths in Expander Digraphs. Tom Bohman, Alan M. Frieze |
| 2001 | Building Low-Diameter P2P Networks. Gopal Pandurangan, Prabhakar Raghavan, Eli Upfal |
| 2001 | Clustering Motion. Sariel Har-Peled |
| 2001 | Coding Theory: Tutorial and Survey. Madhu Sudan |
| 2001 | Compact Oracles for Reachability and Approximate Distances in Planar Digraphs. Mikkel Thorup |
| 2001 | Counting Axioms Do Not Polynomially Simulate Counting Gates. Russell Impagliazzo, Nathan Segerlind |
| 2001 | Designing Networks Incrementally. Adam Meyerson, Kamesh Munagala, Serge A. Plotkin |
| 2001 | Designing Networks for Selfish Users is Hard. Tim Roughgarden |
| 2001 | Deterministic Computation of the Frobenius Form. Arne Storjohann |
| 2001 | Distributions on Level-Sets with Applications to Approximation Algorithms. Aravind Srinivasan |
| 2001 | Expander-Based Constructions of Efficiently Decodable Codes. Venkatesan Guruswami, Piotr Indyk |
| 2001 | Extractors from Reed-Muller Codes. Amnon Ta-Shma, David Zuckerman, Shmuel Safra |
| 2001 | Facility Location with Nonuniform Hard Capacities. Martin Pál, Éva Tardos, Tom Wexler |
| 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 | Game Theory and Mathematical Economics: A Theoretical Computer Scientist's Introduction. Christos H. Papadimitriou |
| 2001 | Glauber Dynamics on Trees and Hyperbolic Graphs. Claire Kenyon, Elchanan Mossel, Yuval Peres |
| 2001 | How Powerful is Adiabatic Quantum Computation?. Wim van Dam, Michele Mosca, Umesh V. Vazirani |
| 2001 | How to Go Beyond the Black-Box Simulation Barrier. Boaz Barak |
| 2001 | Improved Inaproximability Results for MaxClique, Chromatic Number and Approximate Graph Coloring. Subhash Khot |
| 2001 | Informational Complexity and the Direct Sum Problem for Simultaneous Message Complexity. Amit Chakrabarti, Yaoyun Shi, Anthony Wirth, Andrew Chi-Chih Yao |
| 2001 | Linear-time Recognition of Circular-arc Graphs. Ross M. McConnell |
| 2001 | Lower Bounds for Matrix Product. Amir Shpilka |
| 2001 | Lower Bounds for Polynomial Calculus: Non-Binomial Case. Michael Alekhnovich, Alexander A. Razborov |
| 2001 | Lower Bounds for Quantum Communication Complexity. Hartmut Klauck |
| 2001 | On the Average-Case Hardness of CVP. Jin-Yi Cai |
| 2001 | On the Complexity of Many Faces in Arrangements of Circles. Pankaj K. Agarwal, Boris Aronov, Micha Sharir |
| 2001 | On the Impossibility of Basing Trapdoor Functions on Trapdoor Predicates. Yael Gertner, Tal Malkin, Omer Reingold |
| 2001 | Online Facility Location. Adam Meyerson |
| 2001 | Planar Graphs, Negative Weight Edges, Shortest Paths, Near Linear Time. Jittat Fakcharoenphol, Satish Rao |
| 2001 | Query Efficient PCPs with Perfect Completeness. Johan Håstad, Subhash Khot |
| 2001 | Random Evolution in Massive Graphs. William Aiello, Fan R. K. Chung, Linyuan Lu |
| 2001 | Randomly Colouring Graphs with Lower Bounds on Girth and Maximum Degree. Martin E. Dyer, Alan M. Frieze |
| 2001 | Resettably-Sound Zero-Knowledge and its Applications. Boaz Barak, Oded Goldreich, Shafi Goldwasser, Yehuda Lindell |
| 2001 | Resolution is Not Automatizable Unless W[P] is Tractable. Michael Alekhnovich, Alexander A. Razborov |
| 2001 | S Jin-Yi Cai |
| 2001 | Semi-Direct Product in Groups and Zig-Zag Product in Graphs: Connections and Applications. Noga Alon, Alexander Lubotzky, Avi Wigderson |
| 2001 | Sequential and Parallel Algorithms for Mixed Packing and Covering. Neal E. Young |
| 2001 | Simple Extractors for All Min-Entropies and a New Pseudo-Random Generator. Ronen Shaltiel, Christopher Umans |
| 2001 | Simple Routing Strategies for Adversarial Systems. Baruch Awerbuch, Petra Berenbrink, André Brinkmann, Christian Scheideler |
| 2001 | Sorting and Selection with Structured Costs. Anupam Gupta, Amit Kumar |
| 2001 | Source Routing and Scheduling in Packet Networks. Matthew Andrews, Antonio Fernández, Ashish Goel, Lisa Zhang |
| 2001 | Spectral Partitioning of Random Graphs. Frank McSherry |
| 2001 | Testing Random Variables for Independence and Identity. Tugkan Batu, Lance Fortnow, Eldar Fischer, Ravi Kumar, Ronitt Rubinfeld, Patrick White |
| 2001 | Testing Subgraphs in Large Graphs. Noga Alon |
| 2001 | The Complexity of Factors of Multivariate Polynomials. Peter Bürgisser |
| 2001 | The Confluence of Ground Term Rewrite Systems is Decidable in Polynomial Time. Hubert Comon, Guillem Godoy, Robert Nieuwenhuis |
| 2001 | The Natural Work-Stealing Algorithm is Stable. Petra Berenbrink, Tom Friedetzky, Leslie Ann Goldberg |
| 2001 | Three Theorems Regarding Testing Graph Properties. Oded Goldreich, Luca Trevisan |
| 2001 | Tight Approximation Results for General Covering Integer Programs. Stavros G. Kolliopoulos, Neal E. Young |
| 2001 | Traveling with a Pez Dispenser (Or, Routing Issues in MPLS). Anupam Gupta, Amit Kumar, Rajeev Rastogi |
| 2001 | Truthful Mechanisms for One-Parameter Agents. Aaron Archer, Éva Tardos |
| 2001 | Unique Sink Orientations of Cubes. Tibor Szabó, Emo Welzl |
| 2001 | Universally Composable Security: A New Paradigm for Cryptographic Protocols. Ran Canetti |
| 2001 | Vickrey Prices and Shortest Paths: What is an Edge Worth?. John Hershberger, Subhash Suri |
| 2001 | Web Search via Hub Synthesis. Dimitris Achlioptas, Amos Fiat, Anna R. Karlin, Frank McSherry |