| 2000 | A fast algorithm to generate unlabeled necklaces. | Frank Ruskey, Joe Sawada |
| 2000 | Improved Steiner tree approximation in graphs. | Gabriel Robins, Alexander Zelikovsky |
| 2000 | An algebraic method to compute a shortest path of local flips between two tilings. | Eric Rmila |
| 2000 | Strictly non-blocking WDM cross-connects. | April Rasala, Gordon T. Wilfong |
| 2000 | Random three-dimensional tilings of Aztec octahedra and tetrahedra: an extension of domino tilings. | Dana Randall, Gary D. Yngve |
| 2000 | New and improved algorithms for minsum shop scheduling. | Maurice Queyranne, Maxim Sviridenko |
| 2000 | A lower bound for DLL algorithms for | Pavel Pudlk, Russell Impagliazzo |
| 2000 | A new bound for the Carathodory rank of the bases of a matroid. | Jos Coelho de Pina, Jos Soares |
| 2000 | Off-line admission control for general scheduling problems. | Cynthia A. Phillips, R. N. Uma, Joel Wein |
| 2000 | Pattern discovery on character sets and real-valued data: linear bound on irredundant motifs and an efficient polynomial time algorithm. | Laxmi Parida, Isidore Rigoutsos, Aris Floratos, Daniel E. Platt, Yuan Gao |
| 2000 | Nearly optimal computations with structured matrices. | Victor Y. Pan |
| 2000 | Faster deterministic dictionaries. | Rasmus Pagh |
| 2000 | The whole genome assembly of Drosophila. | Gene Myers |
| 2000 | A point-placement strategy for conforming Delaunay tetrahedralization. | Michael Murphy, David M. Mount, Carl W. Gable |
| 2000 | Forcing relations for AND/OR precedence constraints. | Rolf H. Mhring, Martin Skutella, Frederik Stork |
| 2000 | Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks. | S. Thomas McCormick, Akiyoshi Shioura |
| 2000 | Efficient bundle sorting. | Yossi Matias, Eran Segal, Jeffrey Scott Vitter |
| 2000 | Improved bounds on the sample complexity of learning. | Yi Li, Philip M. Long, Aravind Srinivasan |
| 2000 | Fast randomized algorithms for computing minimum {3, 4, 5, 6}-way cuts. | Matthew S. Levine |
| 2000 | On Heilbronn's problem in higher dimension. | Hanno Lefmann |
| 2000 | An optimal algorithm for hyperplane depth in the plane. | Stefan Langerman, William L. Steiger |
| 2000 | On the shared substring alignment problem. | Gad M. Landau, Michal Ziv-Ukelson |
| 2000 | Estimating DNA sequence entropy. | J. Kevin Lanctt, Ming Li, En-Hui Yang |
| 2000 | Construction of visual secret sharing schemes with almost optimal contrast. | Christian Kuhlmann, Hans Ulrich Simon |
| 2000 | On the complexity of bicoloring clique hypergraphs of graphs (extended abstract). | Jan Kratochvl, Zsolt Tuza |