| 2004 | Testing, Optimizaton, and Games. | Mihalis Yannakakis |
| 2004 | A New Algorithm for Optimal Constraint Satisfaction and Its Implications. | Ryan Williams |
| 2004 | On Randomization Versus Synchronization in Distributed Systems. | Hagen Vlzer |
| 2004 | Efficiently Computing Succinct Trade-Off Curves. | Sergei Vassilvitskii, Mihalis Yannakakis |
| 2004 | A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles: (Extended Abstract). | Michael Toftdal |
| 2004 | LA, Permutations, and the Hajs Calculus. | Michael Soltys |
| 2004 | Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas. | Alan Skelley |
| 2004 | Games with Winning Conditions of High Borel Complexity. | Olivier Serre |
| 2004 | Counting in Trees for Free. | Helmut Seidl, Thomas Schwentick, Anca Muscholl, Peter Habermehl |
| 2004 | On the Expressive Power of Monadic Least Fixed Point Logic. | Nicole Schweikardt |
| 2004 | Online Scheduling with Bounded Migration. | Peter Sanders, Naveen Sivadasan, Martin Skutella |
| 2004 | A Syntactic Characterization of Distributive LTL Queries. | Marko Samer, Helmut Veith |
| 2004 | Hardness of String Similarity Search and Other Indexing Problems. | Sleyman Cenk Sahinalp, Andrey Utis |
| 2004 | Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input. | Wojciech Rytter |
| 2004 | Extensional Theories and Rewriting. | Grigore Rosu |
| 2004 | Feasible Proofs and Computations: Partnership and Fusion. | Alexander A. Razborov |
| 2004 | A 2(1/8)-Approximation Algorithm for Rectangle Tiling. | Katarzyna E. Paluch |
| 2004 | Efficient Consistency Proofs for Generalized Queries on a Committed Database. | Rafail Ostrovsky, Charles Rackoff, Adam D. Smith |
| 2004 | The Existence and Efficient Construction of Large Independent Sets in General Random Intersection Graphs. | Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis |
| 2004 | Succinct Representations of Functions. | J. Ian Munro, S. Srinivasa Rao |
| 2004 | A Note on Karr's Algorithm. | Markus Mller-Olm, Helmut Seidl |
| 2004 | A Polynomial Quantum Query Lower Bound for the Set Equality Problem. | Gatis Midrijanis |
| 2004 | Some Results on Effective Randomness. | Wolfgang Merkle, Nenad Mihailovic, Theodore A. Slaman |
| 2004 | A Time Lower Bound for Satisfiability. | Dieter van Melkebeek, Ran Raz |
| 2004 | Transparent Long Proofs: A First PCP Theorem for NP | Klaus Meer |