| 2004 | Deterministic M2M Multicast in Radio Networks: (Extended Abstract). | Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin |
| 2004 | Improved Results for Data Migration and Open Shop Scheduling. | Rajiv Gandhi, Magns M. Halldrsson, Guy Kortsarz, Hadas Shachnai |
| 2004 | Nash Equilibria in Discrete Routing Games with Convex Latency Functions. | Martin Gairing, Thomas Lcking, Marios Mavronicolas, Burkhard Monien, Manuel Rode |
| 2004 | A 2 | Bin Fu, Wei Wang |
| 2004 | Greedy Regular Expression Matching. | Alain Frisch, Luca Cardelli |
| 2004 | A General Technique for Managing Strings in Comparison-Driven Data Structures. | Gianni Franceschini, Roberto Grossi |
| 2004 | Selfish Unsplittable Flows. | Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis |
| 2004 | Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up. | Fedor V. Fomin, Dimitrios M. Thilikos |
| 2004 | Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In. | Fedor V. Fomin, Dieter Kratsch, Ioan Todinca |
| 2004 | Bounded Fixed-Parameter Tractability and log | Jrg Flum, Martin Grohe, Mark Weyer |
| 2004 | Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks. | Lisa Fleischer |
| 2004 | Easily Refutable Subformulas of Large Random 3CNF Formulas. | Uriel Feige, Eran Ofek |
| 2004 | On Graph Problems in a Semi-streaming Model. | Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang |
| 2004 | Interactive Observability in Ludics. | Claudia Faggian |
| 2004 | A Domain Theoretic Account of Picard's Theorem. | Abbas Edalat, Dirk Pattinson |
| 2004 | Locally Consistent Constraint Satisfaction Problems: (Extended Abstract). | Zdenek Dvork, Daniel Krl, Ondrej Pangrc |
| 2004 | Quantum Query Complexity of Some Graph Problems. | Christoph Drr, Mark Heiligman, Peter Hyer, Mehdi Mhalla |
| 2004 | Ecological Turing Machines. | Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin |
| 2004 | Towards an Algebraic Theory of Typed Mobile Processes. | Yuxin Deng, Davide Sangiorgi |
| 2004 | A PTAS for Embedding Hypergraph in a Cycle (Extended Abstract). | Xiaotie Deng, Guojun Li |
| 2004 | Backtracking Games and Inflationary Fixed Points. | Anuj Dawar, Erich Grdel, Stephan Kreutzer |
| 2004 | Solving Two-Variable Word Equations (Extended Abstract). | Robert Dabrowski, Wojciech Plandowski |
| 2004 | Sublinear-Time Approximation for Clustering Via Random Sampling. | Artur Czumaj, Christian Sohler |
| 2004 | Coloring Semirandom Graphs Optimally. | Amin Coja-Oghlan |
| 2004 | Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities. | Bruno Codenotti, Kasturi R. Varadarajan |