| 2004 | Finding k-Connected Subgraphs with Minimum Average Weight. | Prabhakar Gubbala, Balaji Raghavachari |
| 2004 | Arithmetic Circuits for Discrete Logarithms. | Joachim von zur Gathen |
| 2004 | Distributed Games and Distributed Control for Asynchronous Systems. | Paul Gastin, Benjamin Lerman, Marc Zeitoun |
| 2004 | On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications. | Frdric Gardi |
| 2004 | An Improved Communication-Randomness Tradeo. | Martin Frer |
| 2004 | Rotation and Lighting Invariant Template Matching. | Kimmo Fredriksson, Veli Mkinen, Gonzalo Navarro |
| 2004 | Collective Tree Exploration. | Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski, Andrzej Pelc |
| 2004 | Multiple Mobile Agent Rendezvous in a Ring. | Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk |
| 2004 | Embracing the Giant Component. | Abraham Flaxman, David Gamarnik, Gregory B. Sorkin |
| 2004 | List Partitions of Chordal Graphs. | Toms Feder, Pavol Hell, Sulamita Klein, Loana Tito Nogueira, Fbio Protti |
| 2004 | Sublinear Methods for Detecting Periodic Trends in Data Streams. | Funda Ergn, S. Muthukrishnan, Sleyman Cenk Sahinalp |
| 2004 | Global Synchronization in Sensornets. | Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker |
| 2004 | On the Competitiveness of AIMD-TCP within a General Network. | Jeff Edmonds |
| 2004 | Fighting Spam: The Science. | Cynthia Dwork |
| 2004 | Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces. | Volker Diekert, Paul Gastin |
| 2004 | Computation of the Bisection Width for Random d-Regular Graphs. | Josep Daz, Maria J. Serna, Nicholas C. Wormald |
| 2004 | Bidimensional Parameters and Local Treewidth. | Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | Improved Linear Expected-Time Algorithms for Computing Maxima. | H. K. Dai, Xi-Wen Zhang |
| 2004 | Longest Repeats with a Block of Don't Cares. | Maxime Crochemore, Costas S. Iliopoulos, Manal Mohamed, Marie-France Sagot |
| 2004 | An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. | Graham Cormode, S. Muthukrishnan |
| 2004 | Separating Codes: Constructions and Bounds. | Grard D. Cohen, Hans Georg Schaathun |
| 2004 | Measurement Errors Make the Partial Digest Problem NP-Hard. | Mark Cieliebak, Stephan J. Eidenbenz |
| 2004 | Gathering Non-oblivious Mobile Robots. | Mark Cieliebak |
| 2004 | Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank. | Olivier Carton, Chloe Rispal |
| 2004 | Designing Small Keyboards Is Hard. | Jean Cardinal, Stefan Langerman |