| 2004 | A New Model for Selfish Routing. | Thomas Lcking, Marios Mavronicolas, Burkhard Monien, Manuel Rode |
| 2004 | A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees. | Eduardo Sany Laber |
| 2004 | Automata-Based Analysis of Recursive Cryptographic Protocols. | Ralf Ksters, Thomas Wilke |
| 2004 | Sum-Multicoloring on Paths. | Annamria Kovcs |
| 2004 | On Minimizing the Total Weighted Tardiness on a Single Machine. | Stavros G. Kolliopoulos, George Steiner |
| 2004 | Desert Automata and the Finite Substitution Problem. | Daniel Kirsten |
| 2004 | Definability and Regularity in Automatic Structures. | Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan |
| 2004 | Approximation Schemes for Metric Clustering Problems. | Claire Kenyon |
| 2004 | Strongly Stable Matchings in Time O(nm) and Extension to the Hospitals-Residents Problem. | Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch |
| 2004 | Satisfiability Problems Complete for Deterministic Logarithmic Space. | Jan Johannsen |
| 2004 | Integral Symmetric 2-Commodity Flows. | Aubin Jarry |
| 2004 | Periodicity and Unbordered Words: A Proof of Duval?s Conjecture. | Tero Harju, Dirk Nowotka |
| 2004 | Constant Width Planar Computation Characterizes ACC | Kristoffer Arnsfelt Hansen |
| 2004 | Simpler Computation of Single-Source Shortest Paths in Linear Average Time. | Torben Hagerup |
| 2004 | Positional Determinacy of Infinite Games. | Erich Grdel |
| 2004 | A Lower Bound on the Competitive Ratio of Truthful Auctions. | Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks |
| 2004 | On Minimum Circular Arrangement. | Murali K. Ganapathy, Sachin Lodha |
| 2004 | Digraphs Exploration with Little Memory. | Pierre Fraigniaud, David Ilcinkas |
| 2004 | A Simple and Fast Approach for Solving Problems on Planar Graphs. | Fedor V. Fomin, Dimitrios M. Thilikos |
| 2004 | An Algorithmic View on OVSF Code Assignment. | Thomas Erlebach, Riko Jacob, Mats Mihalk, Marc Nunkesser, Gbor Szab, Peter Widmayer |
| 2004 | Optimal and Online Preemptive Scheduling on Uniformly Related Machines. | Toms Ebenlendr, Jir Sgall |
| 2004 | Broadcast in the Rendezvous Model. | Philippe Duchon, Nicolas Hanusse, Nasser Saheb, Akka Zemmari |
| 2004 | Approximation Algorithms for Minimizing Average Distortion. | Kedar Dhamdhere, Anupam Gupta, R. Ravi |
| 2004 | Algorithms for SAT Based on Search in Hamming Balls. | Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert |
| 2004 | On the Expressiveness of Deterministic Transducers over Infinite Trees. | Thomas Colcombet, Christof Lding |