| 2004 | A Case Study of Genome Evolution: From Continuous to Discrete Time Model. Jerzy Tiuryn, Ryszard Rudnicki, Damian Wójtowicz |
| 2004 | A Combinatorial Strongly Subexponential Strategy Improvement Algorithm for Mean Payoff Games. Henrik Björklund, Sven Sandberg, Sergei G. Vorobyov |
| 2004 | A Common Algebraic Description for Probabilistic and Quantum Computations (Extended Abstract). Martin Beaudry, José M. Fernandez, Markus Holzer |
| 2004 | A Generalization of Repetition Threshold. Lucian Ilie, Pascal Ochem, Jeffrey O. Shallit |
| 2004 | A Geometric Approach to Parameterized Algorithms for Domination Problems on Planar Graphs. Henning Fernau, David W. Juedes |
| 2004 | A Hierarchy of Irreducible Sofic Shifts. Marie-Pierre Béal, Francesca Fiorenzi, Dominique Perrin |
| 2004 | A New Dimension Sensitive Property for Cellular Automata. Vincent Bernardi, Bruno Durand, Enrico Formenti, Jarkko Kari |
| 2004 | A Protocol for Serializing Unique Strategies. Marcel Crâsmaru, Christian Glaßer, Kenneth W. Regan, Samik Sengupta |
| 2004 | A Reducibility for the Dot-Depth Hierarchy. Victor L. Selivanov, Klaus W. Wagner |
| 2004 | Agent-Based Information Handling in Large Networks. Robert Elsässer, Ulf Lorenz, Thomas Sauerwald |
| 2004 | Algebraic Recognizability of Languages. Pascal Weil |
| 2004 | All Superlinear Inverse Schemes Are coNP-Hard. Edith Hemaspaandra, Lane A. Hemaspaandra, Harald Hempel |
| 2004 | An Algebraic Generalization of omega-Regular Languages. Zoltán Ésik, Werner Kuich |
| 2004 | An Algorithmic Argument for Nonadaptive Query Complexity Lower Bounds on Advised Quantum Computation (Extended Abstract). Harumichi Nishimura, Tomoyuki Yamakami |
| 2004 | An Elementary Proof for the Non-parametrizability of the Equation xyz=zvx. Elena Petre |
| 2004 | Angles and Lengths in Reconfigurations of Polygons and Polyhedra. Therese Biedl, Anna Lubiw, Michael J. Spriggs |
| 2004 | Approximating Boolean Functions by OBDDs. André Gronemeier |
| 2004 | Approximating Earliest Arrival Flows with Flow-Dependent Transit Times. Nadine Baumann, Ekkehard Köhler |
| 2004 | Boxed Ambients with Communication Interfaces. Eduardo Bonelli, Adriana B. Compagnoni, Mariangiola Dezani-Ciancaglini, Pablo Garralda |
| 2004 | Captive Cellular Automata. Guillaume Theyssier |
| 2004 | Complexity Results in Graph Reconstruction. Edith Hemaspaandra, Lane A. Hemaspaandra, Stanislaw P. Radziszowski, Rahul Tripathi |
| 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 | Computational Aspects of Disjunctive Sequences. Klaus Ambos-Spies, Edgar Busse |
| 2004 | Congestion Games and Coordination Mechanisms. Elias Koutsoupias |
| 2004 | Crossing Number Is Hard for Cubic Graphs. Petr Hlinený |
| 2004 | Decidability of Trajectory-Based Equations. Michael Domaratzki, Kai Salomaa |
| 2004 | Efficient View Point Selection for Silhouettes of Convex Polyhedra. Therese Biedl, Masud Hasan, Alejandro López-Ortiz |
| 2004 | Epistemic Foundation of the Well-Founded Semantics over Bilattices. Yann Loyer, Umberto Straccia |
| 2004 | Equitable Colorings of Bounded Treewidth Graphs. Hans L. Bodlaender, Fedor V. Fomin |
| 2004 | Event Structures for Resolvable Conflict. Rob J. van Glabbeek, Gordon D. Plotkin |
| 2004 | Extraction and Implication of Path Constraints. Yves Andre, Anne-Cécile Caron, Denis Debarbieux, Yves Roos, Sophie Tison |
| 2004 | Generating Paths and Cuts in Multi-pole (Di)graphs. Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan, Kazuhisa Makino |
| 2004 | Generation Problems. Elmar Böhler, Christian Glaßer, Bernhard Schwarz, Klaus W. Wagner |
| 2004 | Geometric Optimization and Unique Sink Orientations of Cubes p. Emo Welzl |
| 2004 | Graph Exploration by a Finite Automaton. Pierre Fraigniaud, David Ilcinkas, Guy Peer, Andrzej Pelc, David Peleg |
| 2004 | Group Coloring and List Group Coloring Are Pi Daniel Král, Pavel Nejedlý |
| 2004 | Improved Bounds and Schemes for the Declustering Problem. Benjamin Doerr, Nils Hebbinghaus, Sören Werth |
| 2004 | Mathematical Foundations of Computer Science 2004, 29th International Symposium, MFCS 2004, Prague, Czech Republic, August 22-27, 2004, Proceedings Jirí Fiala, Václav Koubek, Jan Kratochvíl |
| 2004 | Membership and Reachability Problems for Row-Monomial Transformations. Alexei Lisitsa, Igor Potapov |
| 2004 | Multicoloring: Problems and Techniques. Magnús M. Halldórsson, Guy Kortsarz |
| 2004 | On Approximation Hardness of the Minimum 2SAT-DELETION Problem. Miroslav Chlebík, Janka Chlebíková |
| 2004 | On NC Alfredo De Santis, Giovanni Di Crescenzo, Giuseppe Persiano |
| 2004 | On Polynomially Time Bounded Symmetry of Information. Troy Lee, Andrei Romashchenko |
| 2004 | On Pseudovarieties of Semiring Homomorphisms. Libor Polák |
| 2004 | One Query Reducibilities Between Partial Information Classes. Sebastian Bab, Arfst Nickelsen |
| 2004 | Online Algorithms for Disk Graphs. Ioannis Caragiannis, Aleksei V. Fishkin, Christos Kaklamanis, Evi Papaioannou |
| 2004 | Optimal Preemptive Scheduling for General Target Functions. Leah Epstein, Tamir Tassa |
| 2004 | Optimization, Games, and Quantified Constraint Satisfaction. Hubie Chen, Martin Pál |
| 2004 | PRAM-On-Chip: A Quest for Not-So-Obvious Non-obviousness. Uzi Vishkin |
| 2004 | Packing Directed Cycles Efficiently. Zeev Nutov, Raphael Yuster |
| 2004 | Parallel Knock-Out Schemes in Networks. Hajo Broersma, Fedor V. Fomin, Gerhard J. Woeginger |
| 2004 | Polynomial Time Approximation Schemes and Parameterized Complexity. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia |
| 2004 | Protein Folding in the HP Model on Grid Lattices with Diagonals (Extended Abstract). Hans-Joachim Böckenhauer, Dirk Bongartz |
| 2004 | Scaled Dimension and the Kolmogorov Complexity of Turing-Hard Sets. John M. Hitchcock, María López-Valdés, Elvira Mayordomo |
| 2004 | Schema Evolution for XML: A Consistency-Preserving Approach. Béatrice Bouchou, Denio Duarte, Mirian Halfeld Ferrari Alves, Dominique Laurent, Martin A. Musicante |
| 2004 | Simulating 3D Cellular Automata with 2D Cellular Automata. Victor Poupet |
| 2004 | Some Meet-in-the-Middle Circuit Lower Bounds. Kristoffer Arnsfelt Hansen, Peter Bro Miltersen |
| 2004 | Some Recent Progress in Algorithmic Randomness. Rodney G. Downey |
| 2004 | Structural Model Checking for Communicating Hierarchical Machines. Ruggero Lanotte, Andrea Maggiolo-Schettini, Adriano Peron |
| 2004 | Sublogarithmic Ambiguity. Klaus Wich |
| 2004 | The Bidimensional Theory of Bounded-Genus Graphs. Erik D. Demaine, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | The Complexity of Equivalence and Isomorphism of Systems of Equations over Finite Groups. Gustav Nordh |
| 2004 | The Complexity of Membership Problems for Circuits over Sets of Integers. Stephen D. Travers |
| 2004 | The Dual of Concatenation. Alexander Okhotin |
| 2004 | The Enumerability of P Collapses P to NC. Alina Beygelzimer, Mitsunori Ogihara |
| 2004 | The Price of Anarchy for Polynomial Social Cost. Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien |
| 2004 | Theory and Applied Computing: Observations and Anecdotes. Matthew Brand, Sarah F. Frisken Gibson, Neal Lesh, Joe Marks, Daniel Nikovski, Ronald N. Perry, Jonathan S. Yedidia |
| 2004 | Ubiquitous Parameterization - Invitation to Fixed-Parameter Algorithms. Rolf Niedermeier |
| 2004 | Universal Test for Quantum One-Way Permutations. Akinori Kawachi, Hirotada Kobayashi, Takeshi Koshiba, Raymond H. Putra |
| 2004 | When Can You Play Positionally? Hugo Gimbert, Wieslaw Zielonka |