| 2004 | Structural and algorithmic aspects of massive social networks. | Stephen G. Eubank, V. S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan, Nan Wang |
| 2004 | Optimal online bounded space multidimensional packing. | Leah Epstein, Rob van Stee |
| 2004 | Testing bipartiteness of geometric intersection graphs. | David Eppstein |
| 2004 | Quasiconvex analysis of backtracking algorithms. | David Eppstein |
| 2004 | Approximating Minimum Max-Stretch spanning Trees on unweighted graphs. | Yuval Emek, David Peleg |
| 2004 | Frugality in path auctions. | Edith Elkind, Amit Sahai, Kenneth Steiglitz |
| 2004 | A faster distributed protocol for constructing a minimum spanning tree. | Michael Elkin |
| 2004 | A maiden analysis of Longest Wait First. | Jeff Edmonds, Kirk Pruhs |
| 2004 | Matrix rounding and approximation. | Benjamin Doerr |
| 2004 | Experimental analysis of dynamic all pairs shortest path algorithms. | Camil Demetrescu, Stefano Emiliozzi, Giuseppe F. Italiano |
| 2004 | Interpolation search for non-independent data. | Erik D. Demaine, Thouis R. Jones, Mihai Patrascu |
| 2004 | Retroactive data structures. | Erik D. Demaine, John Iacono, Stefan Langerman |
| 2004 | Equivalence of local treewidth and linear local treewidth and its algorithmic applications. | Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2004 | Subexponential parameterized algorithms on graphs of bounded-genus and | Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | Models of greedy algorithms for graph problems. | Sashka Davis, Russell Impagliazzo |
| 2004 | An exact subexponential-time lattice algorithm for Asian options. | Tian-Shyr Dai, Yuh-Dauh Lyuu |
| 2004 | Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. | Artur Czumaj, Michelangelo Grigni, Papa A. Sissokho, Hairong Zhao |
| 2004 | Approximation schemes for multidimensional packing. | Jos R. Correa, Claire Kenyon |
| 2004 | An improved data stream algorithm for frequency moments. | Don Coppersmith, Ravi Kumar |
| 2004 | Efficient estimation algorithms for neighborhood variance and other moments. | Edith Cohen, Haim Kaplan |
| 2004 | The wake-up problem in multi-hop radio networks. | Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski |
| 2004 | A determinant-based algorithm for counting perfect matchings in a general graph. | Steve Chien |
| 2004 | On finding a guard that sees most and a shop that sells most. | Otfried Cheong, Alon Efrat, Sariel Har-Peled |
| 2004 | Constructing finite field extensions with large order elements. | Qi Cheng |
| 2004 | Invadable self-assembly: combining robustness with efficiency. | Ho-Lin Chen, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, Pablo Moisset de Espans |