| 2001 | Fast computation of low rank matrix. | Dimitris Achlioptas, Frank McSherry |
| 2001 | A sharp threshold in proof complexity. | Dimitris Achlioptas, Paul Beame, Michael S. O. Molloy |
| 2000 | On dual minimum cost flow algorithms (extended abstract). | Jens Vygen |
| 2000 | On transformation of interactive proofs that preserve the prover's complexity. | Salil P. Vadhan |
| 2000 | Near-optimal fully-dynamic graph connectivity. | Mikkel Thorup |
| 2000 | The value of strong inapproximability results for clique. | Aravind Srinivasan |
| 2000 | A guessing game and randomized online algorithms. | Steven S. Seiden |
| 2000 | Clustering for edge-cost minimization (extended abstract). | Leonard J. Schulman |
| 2000 | A PCP characterization of NP with optimal amortized query complexity. | Alex Samorodnitsky, Luca Trevisan |
| 2000 | The program-size complexity of self-assembled squares (extended abstract). | Paul W. K. Rothemund, Erik Winfree |
| 2000 | How tall is a tree? | Bruce A. Reed |
| 2000 | Strictly non-blocking WDM cross-connects for heterogeneous networks. | April Rasala, Gordon T. Wilfong |
| 2000 | On the approximability of the traveling salesman problem (extended abstract). | Christos H. Papadimitriou, Santosh S. Vempala |
| 2000 | epsilon-optimization schemes and L-bit precision: alternative perspectives in combinatorial optimization (extended abstract). | James B. Orlin, Andreas S. Schulz, Sudipta Sengupta |
| 2000 | Matrix-vector product for confluent Cauchy-like matrices with application to confluent rational interpolation. | Vadim Olshevsky, Mohammad Amin Shokrollahi |
| 2000 | Pseudo-random functions and factoring (extended abstract). | Moni Naor, Omer Reingold, Alon Rosen |
| 2000 | Approximate nearest neighbors and sequence comparison with block operations. | S. Muthukrishnan, Sleyman Cenk Sahinalp |
| 2000 | On the decidability of accessibility problems (extended abstract). | Rajeev Motwani, Rina Panigrahy, Vijay A. Saraswat, Suresh Venkatasubramanian |
| 2000 | A new NC-algorithm for finding a perfect matching in bipartite planar and small genus graphs (extended abstract). | Meena Mahajan, Kasturi R. Varadarajan |
| 2000 | A new proof of the weak pigeonhole principle. | Alexis Maciel, Toniann Pitassi, Alan R. Woods |
| 2000 | Near optimal multiple alignment within a band in polynomial time. | Ming Li, Bin Ma, Lusheng Wang |
| 2000 | A matter of degree: improved approximation algorithms for degree-bounded minimum spanning trees. | Jochen Knemann, R. Ravi |
| 2000 | The small-world phenomenon: an algorithmic perspective. | Jon M. Kleinberg |
| 2000 | On quantum and probabilistic communication: Las Vegas and one-way protocols. | Hartmut Klauck |
| 2000 | Parallelization, amplification, and exponential time simulation of quantum interactive proof systems. | Alexei Y. Kitaev, John Watrous |