| 2004 | Fast approximate pattern matching with few indels via embeddings. | Mihai Badoiu, Piotr Indyk |
| 2004 | Simultaneous diophantine approximation with excluded primes. | Lszl Babai, Daniel Stefankovic |
| 2004 | On the diameter of the symmetric group: polynomial bounds. | Lszl Babai, Robert Beals, kos Seress |
| 2004 | The hyperring: a low-congestion deterministic data structure for distributed environments. | Baruch Awerbuch, Christian Scheideler |
| 2004 | Approximate classification via earthmover metrics. | Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, va Tardos |
| 2004 | Routing and scheduling in multihop wireless networks with time-varying channels. | Matthew Andrews, Lisa Zhang |
| 2004 | Point containment in the integer hull of a polyhedron. | Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn |
| 2004 | A characterization of easily testable induced subgraphs. | Noga Alon, Asaf Shapira |
| 2004 | A general approach to online network optimization problems. | Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor |
| 2004 | On colorings of squares of outerplanar graphs. | Geir Agnarsson, Magns M. Halldrsson |
| 2004 | Fault-tolerant gathering algorithms for autonomous mobile robots. | Noa Agmon, David Peleg |
| 2004 | Complexities for generalized models of self-assembly. | Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller |
| 2004 | Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks. | Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir |
| 2004 | Efficient algorithms for bichromatic separability. | Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun |
| 2004 | On the number of rectangular partitions. | Eyal Ackerman, Gill Barequet, Ron Y. Pinter |
| 2004 | Exponential bounds for DPLL below the satisfiability threshold. | Dimitris Achlioptas, Paul Beame, Michael Molloy |
| 2004 | Dynamizing static algorithms, with applications to dynamic trees and history independence. | Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, Shan Leung Maverick Woo |
| 2004 | LAND: stretch (1 + epsilon) locality-aware networks for DHTs. | Ittai Abraham, Dahlia Malkhi, Oren Dobzinski |
| 2003 | Browsing around a digital library. | Ian H. Witten |
| 2003 | Wavelength assignment and generalized interval graph coloring. | Peter Winkler, Lisa Zhang |
| 2003 | On the rectilinear crossing number of complete graphs. | Uli Wagner |
| 2003 | On AC | Mikkel Thorup |
| 2003 | Quick and good facility location. | Mikkel Thorup |
| 2003 | Fault-tolerant facility location. | Chaitanya Swamy, David B. Shmoys |
| 2003 | Allocating vertex pi-guards in simple polygons via pseudo-triangulations. | Bettina Speckmann, Csaba D. Tth |