| 2004 | Generic quantum Fourier transforms. | Cristopher Moore, Daniel N. Rockmore, Alexander Russell |
| 2004 | The pure literal rule threshold and cores in random hypergraphs. | Michael Molloy |
| 2004 | A time efficient Delaunay refinement algorithm. | Gary L. Miller |
| 2004 | Meldable RAM priority queues and minimum directed spanning trees. | Ran Mendelson, Mikkel Thorup, Uri Zwick |
| 2004 | SRPT optimally utilizes faster machines to minimize flow time. | Jason McCullough, Eric Torng |
| 2004 | A certifying algorithm for the consecutive-ones property. | Ross M. McConnell |
| 2004 | Adaptive sampling for quickselect. | Conrado Martinez, Daniel Panario, Alfredo Viola |
| 2004 | Fast mixing for independent sets, colorings and other models on trees. | Fabio Martinelli, Alistair Sinclair, Dror Weitz |
| 2004 | Trade-offs on the location of the core node in a network. | Jean-Franois Macq, Michel X. Goemans |
| 2004 | A stronger bound on Braess's Paradox. | Henry C. Lin, Tim Roughgarden, va Tardos |
| 2004 | Complexity classification of network information flow problems. | April Rasala Lehman, Eric P. Lehman |
| 2004 | Bipartite roots of graphs. | Lap Chi Lau |
| 2004 | Quantum computing. | Raymond Laflamme |
| 2004 | End-to-end packet-scheduling in wireless ad-hoc networks. | V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan |
| 2004 | Navigating nets: simple algorithms for proximity search. | Robert Krauthgamer, James R. Lee |
| 2004 | Locally satisfiable formulas. | Daniel Krl |
| 2004 | Network failure detection and graph connectivity. | Jon M. Kleinberg, Mark Sandler, Aleksandrs Slivkins |
| 2004 | On distributions computable by random walks on graphs. | Guy Kindler, Dan Romik |
| 2004 | Minimizing migrations in fair multiprocessor scheduling of persistent tasks. | Tracy Kimbrel, Baruch Schieber, Maxim Sviridenko |
| 2004 | On broadcasting in heterogenous networks. | Samir Khuller, Yoo Ah Kim |
| 2004 | On the convergence time of a path-vector protocol. | Howard J. Karloff |
| 2004 | On rectangle packing: maximizing benefits. | Klaus Jansen, Guochuan Zhang |
| 2004 | Improved upper bounds for 3-SAT. | Kazuo Iwama, Suguru Tamaki |
| 2004 | Randomized pursuit-evasion with limited visibility. | Volkan Isler, Sampath Kannan, Sanjeev Khanna |
| 2004 | Rank-maximal matchings. | Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch |