| 2004 | Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. | Marek Chrobak, Wojciech Jawor, Jir Sgall, Toms Tich |
| 2004 | Coordination Mechanisms. | George Christodoulou, Elias Koutsoupias, Akash Nanavati |
| 2004 | The Complexity of Equivariant Unification. | James Cheney |
| 2004 | Dynamic Price Sequence and Incentive Compatibility (Extended Abstract). | Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao |
| 2004 | Comparing Recursion, Replication, and Iteration in Process Calculi. | Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro |
| 2004 | The Complexity of Partition Functions. | Andrei A. Bulatov, Martin Grohe |
| 2004 | Model Checking with Multi-valued Logics. | Glenn Bruns, Patrice Godefroid |
| 2004 | An Analog Characterization of Elementarily Computable Functions over the Real Numbers. | Olivier Bournez, Emmanuel Hainry |
| 2004 | Projecting Games on Hypercoherences. | Pierre Boudes |
| 2004 | Tree-Walking Automata Cannot Be Determinized. | Mikolaj Bojanczyk, Thomas Colcombet |
| 2004 | Definitions and Bounds for Self-Healing Key Distribution Schemes. | Carlo Blundo, Paolo D'Arco, Alfredo De Santis |
| 2004 | Approximating Longest Directed Paths and Cycles. | Andreas Bjrklund, Thore Husfeldt, Sanjeev Khanna |
| 2004 | Competition-Induced Preferential Attachment. | Noam Berger, Christian Borgs, Jennifer T. Chayes, Raissa M. D'Souza, Robert D. Kleinberg |
| 2004 | Further Improvements in Competitive Guarantees for QoS Buffering. | Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko |
| 2004 | Group Spreading: A Protocol for Provably Secure Distributed Name Service. | Baruch Awerbuch, Christian Scheideler |
| 2004 | The Power of Verification for One-Parameter Agents. | Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano |
| 2004 | A lambda-Calculus for Resource Separation. | Robert Atkey |
| 2004 | External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs. | Lars Arge, Ulrich Meyer, Laura Toma |
| 2004 | Wavelength Assignment in Optical Networks with Fixed Fiber Capacity. | Matthew Andrews, Lisa Zhang |
| 2004 | Optimal Reachability for Weighted Timed Games. | Rajeev Alur, Mikhail Bernadsky, P. Madhusudan |
| 2004 | Learning a Hidden Subgraph. | Noga Alon, Vera Asodi |
| 2004 | Linear and Branching Metrics for Quantitative Transition Systems. | Luca de Alfaro, Marco Faella, Marille Stoelinga |
| 2004 | Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. | Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson |
| 2004 | Algorithms for Multi-product Pricing. | Gagan Aggarwal, Toms Feder, Rajeev Motwani, An Zhu |
| 2004 | Representing Nested Inductive Types Using W-Types. | Michael Gordon Abbott, Thorsten Altenkirch, Neil Ghani |