| 2002 | Wait-free consensus with infinite arrivals. | James Aspnes, Gauri Shah, Jatin Shah |
| 2002 | Space-efficient approximate Voronoi diagrams. | Sunil Arya, Theocharis Malamatos, David M. Mount |
| 2002 | Fitting algebraic curves to noisy data. | Sanjeev Arora, Subhash Khot |
| 2002 | Cache-oblivious priority queue and graph algorithm applications. | Lars Arge, Michael A. Bender, Erik D. Demaine, Bryan Holland-Minkley, J. Ian Munro |
| 2002 | Stability of load balancing algorithms in dynamic adversarial systems. | Elliot Anshelevich, David Kempe, Jon M. Kleinberg |
| 2002 | Random sampling and approximation of MAX-CSP problems. | Noga Alon, Wenceslas Fernandez de la Vega, Ravi Kannan, Marek Karpinski |
| 2002 | An exponential separation between regular and general resolution. | Michael Alekhnovich, Jan Johannsen, Toniann Pitassi, Alasdair Urquhart |
| 2002 | On paging with locality of reference. | Susanne Albers, Lene M. Favrholdt, Oliver Giel |
| 2002 | On randomized online scheduling. | Susanne Albers |
| 2002 | Approximate counting of inversions in a data stream. | Mikls Ajtai, T. S. Jayram, Ravi Kumar, D. Sivakumar |
| 2002 | The invasiveness of off-line memory checking. | Mikls Ajtai |
| 2002 | 3-manifold knot genus is NP-complet. | Ian Agol, Joel Hass, William P. Thurston |
| 2002 | Tradeoffs in probabilistic packet marking for IP traceback. | Micah Adler |
| 2002 | Combinatorial optimization problems in self-assembly. | Leonard M. Adleman, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, David Kempe, Pablo Moisset de Espans, Paul W. K. Rothemund |
| 2002 | Almost all graphs with average degree 4 are 3-colorable. | Dimitris Achlioptas, Cristopher Moore |
| 2002 | Quantum lower bound for the collision problem. | Scott Aaronson |
| 2001 | Some perspective on computational complexity (abstract). | Andrew Chi-Chih Yao |
| 2001 | Quantum algorithms for solvable groups. | John Watrous |
| 2001 | Estimating true evolutionary distances between genomes. | Li-San Wang, Tandy J. Warnow |
| 2001 | Almost optimal permutation routing on hypercubes. | Berthold Vcking |
| 2001 | Distribution functions of probabilistic automata. | Farrokh Vatan |
| 2001 | Quantum computers that can be simulated classically in polynomial time. | Leslie G. Valiant |
| 2001 | Non-approximability results for optimization problems on bounded degree instances. | Luca Trevisan |
| 2001 | Automata, circuits and hybrids: facets of continuous time. | Boris A. Trakhtenbrot |
| 2001 | Minimax parametric optimization problems and multi-dimensional parametric searching. | Takeshi Tokuyama |