| 2004 | An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract). | Harumichi Nishimura, Tomoyuki Yamakami |
| 2004 | Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. | Rolf Niedermeier |
| 2004 | Complexity of Decision Problems for Simple Regular Expressions. | Wim Martens, Frank Neven, Thomas Schwentick |
| 2004 | Compositional Verification: Decidability Issues Using Graph Substitutions. | Olivier Ly |
| 2004 | Epistemic Foundation of the Well-Founded Semantics over Bilattices. | Yann Loyer, Umberto Straccia |
| 2004 | Membership and Reachability Problems for Row-Monomial Transformations. | Alexei Lisitsa, Igor Potapov |
| 2004 | On Polynomially Time Bounded Symmetry of Information. | Troy Lee, Andrei Romashchenko |
| 2004 | Structural Model Checking for Communicating Hierarchical Machines. | Ruggero Lanotte, Andrea Maggiolo-Schettini, Adriano Peron |
| 2004 | Group Coloring and List Group Coloring Are Pi | Daniel Krl, Pavel Nejedl |
| 2004 | Congestion Games and Coordination Mechanisms. | Elias Koutsoupias |
| 2004 | Universal Test for Quantum One-Way Permutations. | Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra |
| 2004 | A Generalization of Repetition Threshold. | Lucian Ilie, Pascal Ochem, Jeffrey O. Shallit |
| 2004 | Crossing Number Is Hard for Cubic Graphs. | Petr Hlinen |
| 2004 | Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. | John M. Hitchcock, Mara Lpez-Valds, Elvira Mayordomo |
| 2004 | Complexity Results in Graph Reconstruction. | Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi |
| 2004 | All Superlinear Inverse Schemes Are coNP-Hard. | Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
| 2004 | Some Meet-in-the-Middle Circuit Lower Bounds. | Kristoffer Arnsfelt Hansen, Peter Bro Miltersen |
| 2004 | Multicoloring: Problems and Techniques. | Magns M. Halldrsson, Guy Kortsarz |
| 2004 | Approximating Boolean Functions by OBDDs. | Andr Gronemeier |
| 2004 | Event Structures for Resolvable Conflict. | Rob J. van Glabbeek, Gordon D. Plotkin |
| 2004 | When Can You Play Positionally? | Hugo Gimbert, Wieslaw Zielonka |
| 2004 | The Price of Anarchy for Polynomial Social Cost. | Martin Gairing, Thomas Lcking, Marios Mavronicolas, Burkhard Monien |
| 2004 | Graph Exploration by a Finite Automaton. | Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg |
| 2004 | A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs. | Henning Fernau, David W. Juedes |
| 2004 | An Algebraic Generalization of omega-Regular Languages. | Zoltn sik, Werner Kuich |