| 2004 | A Discontinuity in Pattern Inference. Daniel Reidenbach |
| 2004 | A Logspace Approximation Scheme for the Shortest Path Problem for Graphs with Bounded Independence Number. Till Tantau |
| 2004 | A Lower Bound on the Competitive Ratio of Truthful Auctions. Andrew V. Goldberg, Jason D. Hartline, Anna R. Karlin, Michael E. Saks |
| 2004 | A Measured Collapse of the Modal µ-Calculus Alternation Hierarchy. Doron Bustan, Orna Kupferman, Moshe Y. Vardi |
| 2004 | A New Model for Selfish Routing. Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode |
| 2004 | A Randomized Competitive Algorithm for Evaluating Priced AND/OR Trees. Eduardo Sany Laber |
| 2004 | A Simple and Fast Approach for Solving Problems on Planar Graphs. Fedor V. Fomin, Dimitrios M. Thilikos |
| 2004 | Active Context-Free Games. Anca Muscholl, Thomas Schwentick, Luc Segoufin |
| 2004 | Algebraic Results on Quantum Automata. Andris Ambainis, Martin Beaudry, Marats Golovkins, Arnolds Kikusts, Mark Mercer, Denis Thérien |
| 2004 | Algorithms for SAT Based on Search in Hamming Balls. Evgeny Dantsin, Edward A. Hirsch, Alexander Wolpert |
| 2004 | An Algorithmic View on OVSF Code Assignment. Thomas Erlebach, Riko Jacob, Matús Mihalák, Marc Nunkesser, Gábor Szabó, Peter Widmayer |
| 2004 | An Information Theoretic Lower Bound for Broadcasting in Radio Networks. Carlos Brito, Eli Gafni, Shailesh Vaya |
| 2004 | Approximate Path Coloring with Applications to Wavelength Assignment in WDM Optical Networks. Ioannis Caragiannis, Christos Kaklamanis |
| 2004 | Approximation Algorithms for Minimizing Average Distortion. Kedar Dhamdhere, Anupam Gupta, R. Ravi |
| 2004 | Approximation Schemes for Metric Clustering Problems. Claire Kenyon |
| 2004 | Automata-Based Analysis of Recursive Cryptographic Protocols. Ralf Küsters, Thomas Wilke |
| 2004 | Broadcast in the Rendezvous Model. Philippe Duchon, Nicolas Hanusse, Nasser Saheb, Akka Zemmari |
| 2004 | Constant Width Planar Computation Characterizes ACC Kristoffer Arnsfelt Hansen |
| 2004 | Definability and Regularity in Automatic Structures. Bakhadyr Khoussainov, Sasha Rubin, Frank Stephan |
| 2004 | Desert Automata and the Finite Substitution Problem. Daniel Kirsten |
| 2004 | Deterministic Truthful Approximation Mechanisms for Scheduling Related Machines. Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano |
| 2004 | Digraphs Exploration with Little Memory. Pierre Fraigniaud, David Ilcinkas |
| 2004 | Effective Strong Dimension in Algorithmic Information and Computational Complexity. Krishna B. Athreya, John M. Hitchcock, Jack H. Lutz, Elvira Mayordomo |
| 2004 | Efficient Algorithms for Low-Energy Bounded-Hop Broadcast in Ad-Hoc Wireless Networks. Christoph Ambühl, Andrea E. F. Clementi, Miriam Di Ianni, Nissan Lev-Tov, Angelo Monti, David Peleg, Gianluca Rossi, Riccardo Silvestri |
| 2004 | Errata to Analysis of the Harmonic Algorithm for Three Servers. Marek Chrobak, Jirí Sgall |
| 2004 | Identifying Efficiently Solvable Cases of Max CSP. David A. Cohen, Martin C. Cooper, Peter Jeavons, Andrei A. Krokhin |
| 2004 | Individual Communication Complexity: Extended Abstract. Harry Buhrman, Hartmut Klauck, Nikolai K. Vereshchagin, Paul M. B. Vitányi |
| 2004 | Integral Symmetric 2-Commodity Flows. Aubin Jarry |
| 2004 | Lattices with Many Cycles Are Dense. Mårten Trolin |
| 2004 | Local Limit Distributions in Pattern Statistics: Beyond the Markovian Models. Alberto Bertoni, Christian Choffrut, Massimiliano Goldwurm, Violetta Lonati |
| 2004 | Matching Algorithms Are Fast in Sparse Random Graphs. Hannah Bast, Kurt Mehlhorn, Guido Schäfer, Hisao Tamaki |
| 2004 | On Minimizing the Total Weighted Tardiness on a Single Machine. Stavros G. Kolliopoulos, George Steiner |
| 2004 | On Minimum Circular Arrangement. Murali K. Ganapathy, Sachin Lodha |
| 2004 | On Visibility Representation of Plane Graphs. Huaming Zhang, Xin He |
| 2004 | On the Expressiveness of Deterministic Transducers over Infinite Trees. Thomas Colcombet, Christof Löding |
| 2004 | Online Competitive Algorithms for Maximizing Weighted Throughput of Unit Jobs. Yair Bartal, Francis Y. L. Chin, Marek Chrobak, Stanley P. Y. Fung, Wojciech Jawor, Ron Lavi, Jirí Sgall, Tomás Tichý |
| 2004 | Optimal and Online Preemptive Scheduling on Uniformly Related Machines. Tomás Ebenlendr, Jirí Sgall |
| 2004 | Parallel Prefetching and Caching Is Hard. Christoph Ambühl, Birgitta Weber |
| 2004 | Periodicity and Unbordered Words: A Proof of Duval?s Conjecture. Tero Harju, Dirk Nowotka |
| 2004 | Positional Determinacy of Infinite Games. Erich Grädel |
| 2004 | Quantum Identification of Boolean Oracles. Andris Ambainis, Kazuo Iwama, Akinori Kawachi, Hiroyuki Masuda, Raymond H. Putra, Shigeru Yamashita |
| 2004 | Regular Language Matching and Other Decidable Cases of the Satisfiability Problem for Constraints between Regular Open Terms. Sebastian Bala |
| 2004 | STACS 2004, 21st Annual Symposium on Theoretical Aspects of Computer Science, Montpellier, France, March 25-27, 2004, Proceedings Volker Diekert, Michel Habib |
| 2004 | Satisfiability Problems Complete for Deterministic Logarithmic Space. Jan Johannsen |
| 2004 | Simpler Computation of Single-Source Shortest Paths in Linear Average Time. Torben Hagerup |
| 2004 | Solving the 2-Disjoint Paths Problem in Nearly Linear Time. Torsten Tholey |
| 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 | Sum-Multicoloring on Paths. Annamária Kovács |
| 2004 | The Complexity of Boolean Constraint Isomorphism. Elmar Böhler, Edith Hemaspaandra, Steffen Reith, Heribert Vollmer |
| 2004 | The Complexity of Satisfiability Problems over Finite Lattices. Bernhard Schwarz |
| 2004 | The Expected Competitive Ratio for Weighted Completion Time Scheduling. Alexander Souza, Angelika Steger |
| 2004 | The Minimal Logically-Defined NP-Complete Problem. Régis Barbanchon, Etienne Grandjean |
| 2004 | The Plurality Problem with Three Colors. Martin Aigner, Gianluca De Marco, Manuela Montangero |
| 2004 | The Syntactic Graph of a Sofic Shift. Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin |
| 2004 | Time-Space Tradeoff in Derandomizing Probabilistic Logspace. Jin-Yi Cai, Venkatesan T. Chakaravarthy, Dieter van Melkebeek |
| 2004 | Topology Matters: Smoothed Competitiveness of Metrical Task Systems. Guido Schäfer, Naveen Sivadasan |
| 2004 | What Can be Efficiently Reduced to the K-Random Strings? Eric Allender, Harry Buhrman, Michal Koucký |
| 2004 | Worst Case Performance of an Approximation Algorithm for Asymmetric TSP. Anna Palbom |