| 2004 | On the (Im)possibility of Non-interactive Correlation Distillation. | Ke Yang |
| 2004 | O.-Centers: A New Type of Steiner Points for Computing Size-Optimal Quality-Guaranteed Delaunay Triangulations. | Alper ngr |
| 2004 | A Proof System and a Decision Procedure for Equality Logic. | Olga Tveretina, Hans Zantema |
| 2004 | Universal Types and Simulation of Individual Sequences. | Gadiel Seroussi |
| 2004 | Join Irreducible Pseudovarieties, Group Mapping, and Kovcs-Newman Semigroups. | John Rhodes, Benjamin Steinberg |
| 2004 | Approximation Schemes for a Class of Subset Selection Problems. | Kirk Pruhs, Gerhard J. Woeginger |
| 2004 | The Consequences of Imre Simon's Work in the Theory of Automata, Languages, and Semigroups. | Jean-Eric Pin |
| 2004 | Analysis of Scheduling Algorithms for Proportionate Fairness. | Mike Paterson |
| 2004 | Combinatorial Problems on Strings with Applications to Protein Folding. | Alantha Newman, Matthias Ruhl |
| 2004 | Packing Problems with Orthogonal Rotations. | Flvio Keidi Miyazawa, Yoshiko Wakabayashi |
| 2004 | Bisecting and Gossiping in Circulant Graphs. | Bernard Mans, Igor E. Shparlinski |
| 2004 | How Expressions Can Code for Automata. | Sylvain Lombardy, Jacques Sakarovitch |
| 2004 | Nash Equilibria via Polynomial Equations. | Richard J. Lipton, Evangelos Markakis |
| 2004 | Metric Structures in L1: Dimension, Snowflakes, and Average Distortion. | James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | Querying Priced Information in Databases: The Conjunctive Case. | Eduardo Sany Laber, Renato Carmo, Yoshiharu Kohayakawa |
| 2004 | A Constant Approximation Algorithm for Sorting Buffers. | Jens S. Kohrt, Kirk Pruhs |
| 2004 | Advances in the Regularity Method. | Yoshiharu Kohayakawa |
| 2004 | Expected Length of the Longest Common Subsequence for Large Alphabets. | Marcos A. Kiwi, Martin Loebl, Jir Matousek |
| 2004 | Minimum Latency Tours and the k-Traveling Repairmen Problem. | Raja Jothi, Balaji Raghavachari |
| 2004 | Rooted Maximum Agreement Supertrees. | Jesper Jansson, Joseph H.-K. Ng, Kunihiko Sadakane, Wing-Kin Sung |
| 2004 | Complexity of Cycle Length Modularity Problems in Graphs. | Edith Hemaspaandra, Holger Spakowski, Mayur Thakur |
| 2004 | The Complexity of Finding Top-Toda-Equivalence-Class Members. | Lane A. Hemaspaandra, Mitsunori Ogihara, Mohammed Javeed Zaki, Marius Zimand |
| 2004 | A Geometric Approach to the Bisection Method. | Claudio Gutierrez, Flavio Gutierrez, Maria-Cecilia Rivara |
| 2004 | Vertex Disjoint Paths on Clique-Width Bounded Graphs. | Frank Gurski, Egon Wanke |
| 2004 | Procedural Semantics for Fuzzy Disjunctive Programs on Residuated Lattices. | Dusan Guller |