| 2004 | A Constant Approximation Algorithm for Sorting Buffers. Jens S. Kohrt, Kirk Pruhs |
| 2004 | A Geometric Approach to the Bisection Method. Claudio Gutierrez, Flavio Gutierrez, Maria-Cecilia Rivara |
| 2004 | A Proof System and a Decision Procedure for Equality Logic. Olga Tveretina, Hans Zantema |
| 2004 | A Simplified, Dynamic Unified Structure. Mihai Badoiu, Erik D. Demaine |
| 2004 | A Unified Approach to Coding Labeled Trees. Saverio Caminiti, Irene Finocchi, Rossella Petreschi |
| 2004 | Advances in the Regularity Method. Yoshiharu Kohayakawa |
| 2004 | An Improved Communication-Randomness Tradeo. Martin Fürer |
| 2004 | An Improved Data Stream Summary: The Count-Min Sketch and Its Applications. Graham Cormode, S. Muthukrishnan |
| 2004 | Analysis of Scheduling Algorithms for Proportionate Fairness. Mike Paterson |
| 2004 | Another View of the Gaussian Algorithm. Ali Akhavi, Céline Moreira Dos Santos |
| 2004 | Approximating the Expressive Power of Logics in Finite Models. Argimiro Arratia, Carlos E. Ortiz |
| 2004 | Approximation Schemes for a Class of Subset Selection Problems. Kirk Pruhs, Gerhard J. Woeginger |
| 2004 | Arithmetic Circuits for Discrete Logarithms. Joachim von zur Gathen |
| 2004 | Automata for Arithmetic Meyer Sets. Shigeki Akiyama, Frédérique Bassino, Christiane Frougny |
| 2004 | Bidimensional Parameters and Local Treewidth. Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | Bisecting and Gossiping in Circulant Graphs. Bernard Mans, Igor E. Shparlinski |
| 2004 | Collective Tree Exploration. Pierre Fraigniaud, Leszek Gasieniec, Dariusz R. Kowalski, Andrzej Pelc |
| 2004 | Combinatorial Problems on Strings with Applications to Protein Folding. Alantha Newman, Matthias Ruhl |
| 2004 | Complementation of Rational Sets on Scattered Linear Orderings of Finite Rank. Olivier Carton, Chloe Rispal |
| 2004 | Complexity of Cycle Length Modularity Problems in Graphs. Edith Hemaspaandra, Holger Spakowski, Mayur Thakur |
| 2004 | Computation of the Bisection Width for Random d-Regular Graphs. Josep Díaz, Maria J. Serna, Nicholas C. Wormald |
| 2004 | Constrained Integer Partitions. Christian Borgs, Jennifer T. Chayes, Stephan Mertens, Boris G. Pittel |
| 2004 | Cost-Optimal Trees for Ray Shooting. Hervé Brönnimann, Marc Glisse |
| 2004 | Designing Small Keyboards Is Hard. Jean Cardinal, Stefan Langerman |
| 2004 | Distributed Games and Distributed Control for Asynchronous Systems. Paul Gastin, Benjamin Lerman, Marc Zeitoun |
| 2004 | Effciently Computing the Density of Regular Languages. Manuel Bodirsky, Tobias Gärtner, Timo von Oertzen, Jan Schwinghammer |
| 2004 | Embracing the Giant Component. Abraham Flaxman, David Gamarnik, Gregory B. Sorkin |
| 2004 | Encoding Homotopy of Paths in the Plane. Sergei Bespamyatnikh |
| 2004 | Expected Length of the Longest Common Subsequence for Large Alphabets. Marcos A. Kiwi, Martin Loebl, Jirí Matousek |
| 2004 | Fighting Spam: The Science. Cynthia Dwork |
| 2004 | Finding k-Connected Subgraphs with Minimum Average Weight. Prabhakar Gubbala, Balaji Raghavachari |
| 2004 | Gathering Non-oblivious Mobile Robots. Mark Cieliebak |
| 2004 | Generating Maximal Independent Sets for Hypergraphs with Bounded Edge-Intersections. Endre Boros, Khaled M. Elbassioni, Vladimir Gurvich, Leonid Khachiyan |
| 2004 | Global Synchronization in Sensornets. Jeremy Elson, Richard M. Karp, Christos H. Papadimitriou, Scott Shenker |
| 2004 | How Expressions Can Code for Automata. Sylvain Lombardy, Jacques Sakarovitch |
| 2004 | Improved Linear Expected-Time Algorithms for Computing Maxima. H. K. Dai, Xi-Wen Zhang |
| 2004 | Join Irreducible Pseudovarieties, Group Mapping, and Kovács-Newman Semigroups. John Rhodes, Benjamin Steinberg |
| 2004 | LATIN 2004: Theoretical Informatics, 6th Latin American Symposium, Buenos Aires, Argentina, April 5-8, 2004, Proceedings Martin Farach-Colton |
| 2004 | List Partitions of Chordal Graphs. Tomás Feder, Pavol Hell, Sulamita Klein, Loana Tito Nogueira, Fábio Protti |
| 2004 | Longest Repeats with a Block of Don't Cares. Maxime Crochemore, Costas S. Iliopoulos, Manal Mohamed, Marie-France Sagot |
| 2004 | Measurement Errors Make the Partial Digest Problem NP-Hard. Mark Cieliebak, Stephan J. Eidenbenz |
| 2004 | Metric Structures in L1: Dimension, Snowflakes, and Average Distortion. James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | Minimum Latency Tours and the k-Traveling Repairmen Problem. Raja Jothi, Balaji Raghavachari |
| 2004 | Multiple Mobile Agent Rendezvous in a Ring. Paola Flocchini, Evangelos Kranakis, Danny Krizanc, Nicola Santoro, Cindy Sawchuk |
| 2004 | Nash Equilibria via Polynomial Equations. Richard J. Lipton, Evangelos Markakis |
| 2004 | O.-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations. Alper Üngör |
| 2004 | On Partitioning Interval and Circular-Arc Graphs into Proper Interval Subgraphs with Applications. Frédéric Gardi |
| 2004 | On the (Im)possibility of Non-interactive Correlation Distillation. Ke Yang |
| 2004 | On the Competitiveness of AIMD-TCP within a General Network. Jeff Edmonds |
| 2004 | Packing Problems with Orthogonal Rotations. Flávio Keidi Miyazawa, Yoshiko Wakabayashi |
| 2004 | Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices. Dusan Guller |
| 2004 | Pure Future Local Temporal Logics Are Expressively Complete for Mazurkiewicz Traces. Volker Diekert, Paul Gastin |
| 2004 | Querying Priced Information in Databases: The Conjunctive Case. Eduardo Sany Laber, Renato Carmo, Yoshiharu Kohayakawa |
| 2004 | Rooted Maximum Agreement Supertrees. Jesper Jansson, Joseph H.-K. Ng, Kunihiko Sadakane, Wing-Kin Sung |
| 2004 | Rotation and Lighting Invariant Template Matching. Kimmo Fredriksson, Veli Mäkinen, Gonzalo Navarro |
| 2004 | Sampling Grid Colorings with Fewer Colors. Dimitris Achlioptas, Michael S. O. Molloy, Cristopher Moore, Frank Van Bussel |
| 2004 | Separating Codes: Constructions and Bounds. Gérard D. Cohen, Hans Georg Schaathun |
| 2004 | Server Scheduling in the Weighted l Nikhil Bansal, Kirk Pruhs |
| 2004 | Space-E.cient Algorithms for Computing the Convex Hull of a Simple Polygonal Line in Linear Time. Hervé Brönnimann, Timothy M. Chan |
| 2004 | Sublinear Methods for Detecting Periodic Trends in Data Streams. Funda Ergün, S. Muthukrishnan, Süleyman Cenk Sahinalp |
| 2004 | The Complexity of Finding Top-Toda-Equivalence-Class Members. Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed Javeed Zaki, Marius Zimand |
| 2004 | The Consequences of Imre Simon's Work in the Theory of Automata, Languages, and Semigroups. Jean-Eric Pin |
| 2004 | Universal Types and Simulation of Individual Sequences. Gadiel Seroussi |
| 2004 | Vertex Disjoint Paths on Clique-Width Bounded Graphs. Frank Gurski, Egon Wanke |