| 2004 | Entropy as a Fixed Point. | Keye Martin |
| 2004 | Property Testing of Regular Tree Languages. | Frdric Magniez, Michel de Rougemont |
| 2004 | Complexity of Pseudoknot Prediction in Simple Models. | Rune B. Lyngs |
| 2004 | Word Problems on Compressed Words. | Markus Lohrey |
| 2004 | Almost Optimal Decentralized Routing in Long-Range Contact Networks. | Emmanuelle Lebhar, Nicolas Schabanel |
| 2004 | A Calculus of Coroutines. | James Laird |
| 2004 | Regular Solutions of Language Inequalities and Well Quasi-orders. | Michal Kunc |
| 2004 | The Black-Box Complexity of Nearest Neighbor Search. | Robert Krauthgamer, James R. Lee |
| 2004 | A Faster Algorithm for Minimum Cycle Basis of Graphs. | Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch |
| 2004 | A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems. | Shin-ya Katsumata |
| 2004 | Fairness to All While Downsizing. | Bala Kalyanasundaram, Mahendran Velauthapillai |
| 2004 | Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design. | Raja Jothi, Balaji Raghavachari |
| 2004 | Universality in Quantum Computation. | Emmanuel Jeandel |
| 2004 | Closest Pair Problems in Very High Dimensions. | Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat |
| 2004 | Simple Permutations Mix Well. | Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff |
| 2004 | What Do Program Logics and Type Systems Have in Common? | Martin Hofmann |
| 2004 | The Past, Present, and Future of Web Search Engines p. | Monika Henzinger |
| 2004 | Optimal Website Design with the Constrained Subtree Selection Problem. | Brent Heeringa, Micah Adler |
| 2004 | Communication Versus Computation. | Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh |
| 2004 | Self-Adjusting Computation. | Robert Harper |
| 2004 | The Minimum-Entropy Set Cover Problem. | Eran Halperin, Richard M. Karp |
| 2004 | Testing Monotonicity over Graph Products. | Shirley Halevy, Eyal Kushilevitz |
| 2004 | A Categorical Model for the Geometry of Interaction. | Esfandiar Haghverdi, Philip J. Scott |
| 2004 | Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). | Venkatesan Guruswami, Piotr Indyk |
| 2004 | Syntactic Control of Concurrency. | Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong |