| 2000 | Testing and spot-checking of data streams (extended abstract). | Joan Feigenbaum, Sampath Kannan, Martin Strauss, Mahesh Viswanathan |
| 2000 | Restructuring ordered binary trees. | William S. Evans, David G. Kirkpatrick |
| 2000 | Movement minimization in conveyor flow shop processing. | Wolfgang Espelage, Egon Wanke |
| 2000 | Finite-resolution hidden surface removal. | Jeff Erickson |
| 2000 | Orthogonal graph drawing with constraints. | Markus Eiglsperger, Ulrich Fmeier, Michael Kaufmann |
| 2000 | On incremental rendering of silhouette maps of polyhedral scene. | Alon Efrat, Leonidas J. Guibas, Olaf A. Hall-Holt, Li Zhang |
| 2000 | Sweeping simple polygons with a chain of guards. | Alon Efrat, Leonidas J. Guibas, Sariel Har-Peled, David C. Lin, Joseph S. B. Mitchell, T. M. Murali |
| 2000 | An extension of path coupling and its application to the Glauber dynamics for graph colourings (extended abstract). | Martin E. Dyer, Leslie Ann Goldberg, Catherine S. Greenhill, Mark Jerrum, Michael Mitzenmacher |
| 2000 | The complexity of counting graph homomorphisms (extended abstract). | Martin E. Dyer, Catherine S. Greenhill |
| 2000 | Typical random 3-SAT formulae and the satisfiability threshold. | Olivier Dubois, Yacine Boufkhad, Jacques Mandler |
| 2000 | Evaluating the cylindricity of a nominally cylindrical point set. | Olivier Devillers, Franco P. Preparata |
| 2000 | Adaptive set intersections, unions, and differences. | Erik D. Demaine, Alejandro Lpez-Ortiz, J. Ian Munro |
| 2000 | Commuting with delay prone buses. | Mayur Datar, Abhiram G. Ranade |
| 2000 | A (2 + epsilon)-approximation scheme for minimum domination on circle graphs. | Mirela Damian-Iordache, Sriram V. Pemmaraju |
| 2000 | Coloring non-uniform hypergraphs: a new algorithmic approach to the general Lovsz local lemma. | Artur Czumaj, Christian Scheideler |
| 2000 | Algorithms for optimizing production DNA sequencing. | va Czabarka, Goran Konjevod, Madhav V. Marathe, Allon G. Percus, David C. Torney |
| 2000 | Sharing one secret vs. sharing many secrets: tight bounds on the average improvement ratio. | Giovanni Di Crescenzo |
| 2000 | Communication complexity of document exchange. | Graham Cormode, Mike Paterson, Sleyman Cenk Sahinalp, Uzi Vishkin |
| 2000 | On the temporal HZY compression scheme. | Z. Cohen, Yossi Matias, S. Muthukrishnan, Sleyman Cenk Sahinalp, Jacob Ziv |
| 2000 | Recognizing dart-free perfect graphs. | Vasek Chvtal, Jean Fonlupt, L. Sun, Abdelhamid Zemirline |
| 2000 | Deterministic broadcasting in unknown radio networks. | Bogdan S. Chlebus, Leszek Gasieniec, Alan Gibbons, Andrzej Pelc, Wojciech Rytter |
| 2000 | A dynamic programming approach to de novo peptide sequencing via tandem mass spectrometry. | Ting Chen, Ming-Yang Kao, Matthew Tepel, John Rush, George M. Church |
| 2000 | Optimizing the sum of linear fractional functions and applications. | Danny Z. Chen, Ovidiu Daescu, Yang Dai, Naoki Katoh, Xiaodong Wu, Jinhui Xu |
| 2000 | A PTAS for the multiple knapsack problem. | Chandra Chekuri, Sanjeev Khanna |
| 2000 | Escaping a grid by edge-disjoint paths. | Wun-Tat Chan, Francis Y. L. Chin, Hing-Fung Ting |