| 2004 | Approximate Nearest Neighbor under edit distance via product metrics. | Piotr Indyk |
| 2004 | On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. | Nicole Immorlica, David R. Karger, Maria Minkoff, Vahab S. Mirrokni |
| 2004 | A note on the nearest neighbor in growth-restricted metrics. | Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao |
| 2004 | Variable length path coupling. | Thomas P. Hayes, Eric Vigoda |
| 2004 | Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. | Venkatesan Guruswami, Piotr Indyk |
| 2004 | When indexing equals compression: experiments with compressing suffix arrays and applications. | Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter |
| 2004 | Algorithms for infinite huffman-codes. | Mordecai J. Golin, Kin Keung Ma |
| 2004 | Covering minimum spanning trees of random subgraphs. | Michel X. Goemans, Jan Vondrk |
| 2004 | Finding dominators revisited: extended abstract. | Loukas Georgiadis, Robert Endre Tarjan |
| 2004 | Succinct ordinal trees with level-ancestor queries. | Richard F. Geary, Rajeev Raman, Venkatesh Raman |
| 2004 | Polynomial interpolation from multiples. | Joachim von zur Gathen, Igor E. Shparlinski |
| 2004 | Fair and efficient router congestion control. | Xiaojie Gao, Kamal Jain, Leonard J. Schulman |
| 2004 | Optimal routing in Chord. | Prasanna Ganesan, Gurmeet Singh Manku |
| 2004 | On contract-and-refine transformations between phylogenetic trees. | Ganeshkumar Ganapathy, Vijaya Ramachandran, Tandy J. Warnow |
| 2004 | Linear phase transition in random linear constraint satisfaction problems. | David Gamarnik |
| 2004 | Slow mixing of Glauber dynamics for the hard-core model on the hypercube. | David J. Galvin, Prasad Tetali |
| 2004 | Finding a long directed cycle. | Harold N. Gabow, Shuxin Nie |
| 2004 | Special edges, and approximating the smallest directed | Harold N. Gabow |
| 2004 | Proximity Mergesort: optimal in-place sorting in the cache-oblivious model. | Gianni Franceschini |
| 2004 | A fast approximation scheme for fractional covering problems with variable upper bounds. | Lisa Fleischer |
| 2004 | The number of bit comparisons used by Quicksort: an average-case analysis. | James Allen Fill, Svante Janson |
| 2004 | Compression boosting in optimal linear time using the Burrows-Wheeler Transform. | Paolo Ferragina, Giovanni Manzini |
| 2004 | Minimizing the stabbing number of matchings, trees, and triangulations. | Sndor P. Fekete, Marco E. Lbbecke, Henk Meijer |
| 2004 | Output-sensitive construction of the union of triangles. | Eti Ezra, Micha Sharir |
| 2004 | Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. | William S. Evans, David G. Kirkpatrick |