| 2001 | (1+epsilon, beta)-spanner constructions for general graphs. Michael Elkin, David Peleg |
| 2001 | A constant factor approximation for the single sink edge installation problems. Sudipto Guha, Adam Meyerson, Kamesh Munagala |
| 2001 | A new protocol and lower bounds for quantum coin flipping. Andris Ambainis |
| 2001 | A polynomial-time approximation algorithm for the permanent of a matrix with non-negative entries. Mark Jerrum, Alistair Sinclair, Eric Vigoda |
| 2001 | A read-once branching program lower bound of Omega(2 Beate Bollig, Philipp Woelfel |
| 2001 | A sharp threshold in proof complexity. Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy |
| 2001 | A sieve algorithm for the shortest lattice vector problem. Miklós Ajtai, Ravi Kumar, D. Sivakumar |
| 2001 | A tight bound for the complexity of voroni diagrams under polyhedral convex distance functions in 3D. Christian Icking, Lihong Ma |
| 2001 | Algorithms for minimizing weighted flow time. Chandra Chekuri, Sanjeev Khanna, An Zhu |
| 2001 | Algorithms, games, and the internet. Christos H. Papadimitriou |
| 2001 | Almost optimal permutation routing on hypercubes. Berthold Vöcking |
| 2001 | Anti-presistence: history independent data structures. Moni Naor, Vanessa Teague |
| 2001 | Applications of approximation algorithms to cooperative games. Kamal Jain, Vijay V. Vazirani |
| 2001 | Approximate distance oracles. Mikkel Thorup, Uri Zwick |
| 2001 | Approximating min-sum Yair Bartal, Moses Charikar, Danny Raz |
| 2001 | Approximation algorithms for MAX-3-CUT and other problems via complex semidefinite programming. Michel X. Goemans, David P. Williamson |
| 2001 | Approximation algorithms for constrained for constrained node weighted steiner tree problems. Anna Moss, Yuval Rabani |
| 2001 | Automata, circuits and hybrids: facets of continuous time. Boris A. Trakhtenbrot |
| 2001 | Biased dictionaries with fast insert/deletes. Funda Ergün, Süleyman Cenk Sahinalp, Jonathan Sharp, Rakesh K. Sinha |
| 2001 | Black-box concurrent zero-knowledge requires Omega~(log n) rounds. Ran Canetti, Joe Kilian, Erez Petrank, Alon Rosen |
| 2001 | Buffer overflow management in QoS switches. Alexander Kesselman, Zvi Lotker, Yishay Mansour, Boaz Patt-Shamir, Baruch Schieber, Maxim Sviridenko |
| 2001 | Clustering to minimize the sum of cluster diameters. Moses Charikar, Rina Panigrahy |
| 2001 | Colouring graphs when the number of colours is nearly the maximum degree. Michael Molloy, Bruce A. Reed |
| 2001 | Communication preserving protocols for secure function evaluation. Moni Naor, Kobbi Nissim |
| 2001 | Compatible sequences and a slow Winkler percolation. Péter Gács |
| 2001 | Complex tilings. Bruno Durand, Leonid A. Levin, Alexander Shen |
| 2001 | Computing crossing numbers in quadratic time. Martin Grohe |
| 2001 | Computing with continuous-time Liapunov systems. Jirí Síma, Pekka Orponen |
| 2001 | Concurrent and resettable zero-knowledge in poly-loalgorithm rounds. Joe Kilian, Erez Petrank |
| 2001 | Conditions on input vectors for consensus solvability in asynchronous distributed systems. Achour Mostéfaoui, Sergio Rajsbaum, Michel Raynal |
| 2001 | Data-streams and histograms. Sudipto Guha, Nick Koudas, Kyuseok Shim |
| 2001 | Decidability of string graphs. Marcus Schaefer, Daniel Stefankovic |
| 2001 | Distribution functions of probabilistic automata. Farrokh Vatan |
| 2001 | Dynamic TCP acknowledgement and other stories about e/(e-1). Anna R. Karlin, Claire Kenyon, Dana Randall |
| 2001 | Edge isoperimetry and rapid mixing on matroids and geometric Markov chains. Ravi Montenegro, Jung-Bae Son |
| 2001 | Estimating true evolutionary distances between genomes. Li-San Wang, Tandy J. Warnow |
| 2001 | Euler paths in series parallel graphs. S. Rao Kosaraju |
| 2001 | Excellent codes from modular curves. Noam D. Elkies |
| 2001 | Explicit lower bound of Oded Lachish, Ran Raz |
| 2001 | Extractor codes. Amnon Ta-Shma, David Zuckerman |
| 2001 | Fast computation of low rank matrix. Dimitris Achlioptas, Frank McSherry |
| 2001 | Fully-dynamic min-cut. Mikkel Thorup |
| 2001 | Interaction in quantum communication and the complexity of set disjointness. Hartmut Klauck, Ashwin Nayak, Amnon Ta-Shma, David Zuckerman |
| 2001 | Learning DNF in time 2 Adam R. Klivans, Rocco A. Servedio |
| 2001 | Learning mixtures of arbitrary gaussians. Sanjeev Arora, Ravi Kannan |
| 2001 | Local search heuristic for k-median and facility location problems. Vijay Arya, Naveen Garg, Rohit Khandekar, Adam Meyerson, Kamesh Munagala, Vinayaka Pandit |
| 2001 | Loss-less condensers, unbalanced expanders, and extractors. Amnon Ta-Shma, Christopher Umans, David Zuckerman |
| 2001 | Lower bounds for intersection searching and fractional cascading in higher dimension. Bernard Chazelle, Ding Liu |
| 2001 | Lower bounds for matrix product, in bounded depth circuits with arbitrary gates. Ran Raz, Amir Shpilka |
| 2001 | Minimax parametric optimization problems and multi-dimensional parametric searching. Takeshi Tokuyama |
| 2001 | Non-approximability results for optimization problems on bounded degree instances. Luca Trevisan |
| 2001 | Non-clairvoyant scheduling to minimize the average flow time on single and parallel machines. Luca Becchetti, Stefano Leonardi |
| 2001 | On optimal slicing of parallel programs. Markus Müller-Olm, Helmut Seidl |
| 2001 | On the cell probe complexity of membership and perfect hashing. Rasmus Pagh |
| 2001 | On the integrality ratio of semidefinite relaxations of MAX CUT. Uriel Feige, Gideon Schechtman |
| 2001 | One line and n points. Bernd Gärtner, József Solymosi, Falk Tschirschnitz, Emo Welzl, Pavel Valtr |
| 2001 | One-dimensional quantum walks. Andris Ambainis, Eric Bach, Ashwin Nayak, Ashvin Vishwanath, John Watrous |
| 2001 | Online server allocation in a server farm via benefit task systems. T. S. Jayram, Tracy Kimbrel, Robert Krauthgamer, Baruch Schieber, Maxim Sviridenko |
| 2001 | Optimal outlier removal in high-dimensional. John Dunagan, Santosh S. Vempala |
| 2001 | Optimal static range reporting in one dimension. Stephen Alstrup, Gerth Stølting Brodal, Theis Rauhe |
| 2001 | Private approximation of NP-hard functions. Shai Halevi, Robert Krauthgamer, Eyal Kushilevitz, Kobbi Nissim |
| 2001 | Proceedings on 33rd Annual ACM Symposium on Theory of Computing, July 6-8, 2001, Heraklion, Crete, Greece Jeffrey Scott Vitter, Paul G. Spirakis, Mihalis Yannakakis |
| 2001 | Profit-earning facility location. Adam Meyerson |
| 2001 | Provisioning a virtual private network: a network design problem for multicommodity flow. Anupam Gupta, Jon M. Kleinberg, Amit Kumar, Rajeev Rastogi, Bülent Yener |
| 2001 | Quantitative solution of omega-regular games. Luca de Alfaro, Rupak Majumdar |
| 2001 | Quantum algorithms for solvable groups. John Watrous |
| 2001 | Quantum computers that can be simulated classically in polynomial time. Leslie G. Valiant |
| 2001 | Quantum mechanical algorithms for the nonabelian hidden subgroup problem. Michelangelo Grigni, Leonard J. Schulman, Monica Vazirani, Umesh V. Vazirani |
| 2001 | Quantum walks on graphs. Dorit Aharonov, Andris Ambainis, Julia Kempe, Umesh V. Vazirani |
| 2001 | Randomness efficient identity testing of multivariate polynomials. Adam R. Klivans, Daniel A. Spielman |
| 2001 | Regular resolution lower bounds for the weak pigeonhole principle. Toniann Pitassi, Ran Raz |
| 2001 | Running time and program size for self-assembled squares. Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang |
| 2001 | Sampling algorithms: lower bounds and applications. Ziv Bar-Yossef, Ravi Kumar, D. Sivakumar |
| 2001 | Sharp threshold and scaling window for the integer partitioning problem. Christian Borgs, Jennifer T. Chayes, Boris G. Pittel |
| 2001 | Smoothed analysis of algorithms: why the simplex algorithm usually takes polynomial time. Daniel A. Spielman, Shang-Hua Teng |
| 2001 | Some perspective on computational complexity (abstract). Andrew Chi-Chih Yao |
| 2001 | Sparse polynomial approximation in finite fields. Igor E. Shparlinski |
| 2001 | Spatial gossip and resource location protocols. David Kempe, Jon M. Kleinberg, Alan J. Demers |
| 2001 | Spectral analysis of data. Yossi Azar, Amos Fiat, Anna R. Karlin, Frank McSherry, Jared Saia |
| 2001 | Stackelberg scheduling strategies. Tim Roughgarden |
| 2001 | Testing metric properties. Michal Parnas, Dana Ron |
| 2001 | Testing of matrix properties. Eldar Fischer, Ilan Newman |
| 2001 | The complexity of analytic tableaux. Noriko H. Arai, Toniann Pitassi, Alasdair Urquhart |
| 2001 | The complexity of maximal constraint languages. Andrei A. Bulatov, Andrei A. Krokhin, Peter Jeavons |
| 2001 | The price of selfish routing. Marios Mavronicolas, Paul G. Spirakis |
| 2001 | The round complexity of verifiable secret sharing and secure multicast. Rosario Gennaro, Yuval Ishai, Eyal Kushilevitz, Tal Rabin |
| 2001 | When is the evaluation of conjunctive queries tractable? Martin Grohe, Thomas Schwentick, Luc Segoufin |