| 2004 | A 2 Bin Fu, Wei Wang |
| 2004 | A 2(1/8)-Approximation Algorithm for Rectangle Tiling. Katarzyna E. Paluch |
| 2004 | A Calculus of Coroutines. James Laird |
| 2004 | A Calibration of Ineffective Theorems of Analysis in a Hierarchy of Semi-classical Logical Principles: (Extended Abstract). Michael Toftdal |
| 2004 | A Categorical Model for the Geometry of Interaction. Esfandiar Haghverdi, Philip J. Scott |
| 2004 | A Domain Theoretic Account of Picard's Theorem. Abbas Edalat, Dirk Pattinson |
| 2004 | A Faster Algorithm for Minimum Cycle Basis of Graphs. Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch |
| 2004 | A General Technique for Managing Strings in Comparison-Driven Data Structures. Gianni Franceschini, Roberto Grossi |
| 2004 | A Generalisation of Pre-logical Predicates to Simply Typed Formal Systems. Shin-ya Katsumata |
| 2004 | A New Algorithm for Optimal Constraint Satisfaction and Its Implications. Ryan Williams |
| 2004 | A Note on Karr's Algorithm. Markus Müller-Olm, Helmut Seidl |
| 2004 | A PTAS for Embedding Hypergraph in a Cycle (Extended Abstract). Xiaotie Deng, Guojun Li |
| 2004 | A Polynomial Quantum Query Lower Bound for the Set Equality Problem. Gatis Midrijanis |
| 2004 | A Syntactic Characterization of Distributive LTL Queries. Marko Samer, Helmut Veith |
| 2004 | A Time Lower Bound for Satisfiability. Dieter van Melkebeek, Ran Raz |
| 2004 | A lambda-Calculus for Resource Separation. Robert Atkey |
| 2004 | Algorithms for Multi-product Pricing. Gagan Aggarwal, Tomás Feder, Rajeev Motwani, An Zhu |
| 2004 | Almost Optimal Decentralized Routing in Long-Range Contact Networks. Emmanuelle Lebhar, Nicolas Schabanel |
| 2004 | An Analog Characterization of Elementarily Computable Functions over the Real Numbers. Olivier Bournez, Emmanuel Hainry |
| 2004 | Approximating Longest Directed Paths and Cycles. Andreas Björklund, Thore Husfeldt, Sanjeev Khanna |
| 2004 | Approximation Algorithms for the Capacitated Minimum Spanning Tree Problem and Its Variants in Network Design. Raja Jothi, Balaji Raghavachari |
| 2004 | Automata, Languages and Programming: 31st International Colloquium, ICALP 2004, Turku, Finland, July 12-16, 2004. Proceedings Josep Díaz, Juhani Karhumäki, Arto Lepistö, Donald Sannella |
| 2004 | Backtracking Games and Inflationary Fixed Points. Anuj Dawar, Erich Grädel, Stephan Kreutzer |
| 2004 | Bounded Fixed-Parameter Tractability and log Jörg Flum, Martin Grohe, Mark Weyer |
| 2004 | Closest Pair Problems in Very High Dimensions. Piotr Indyk, Moshe Lewenstein, Ohad Lipsky, Ely Porat |
| 2004 | Coloring Semirandom Graphs Optimally. Amin Coja-Oghlan |
| 2004 | Communication Versus Computation. Prahladh Harsha, Yuval Ishai, Joe Kilian, Kobbi Nissim, Srinivasan Venkatesh |
| 2004 | Comparing Recursion, Replication, and Iteration in Process Calculi. Nadia Busi, Maurizio Gabbrielli, Gianluigi Zavattaro |
| 2004 | Competition-Induced Preferential Attachment. Noam Berger, Christian Borgs, Jennifer T. Chayes, Raissa M. D'Souza, Robert D. Kleinberg |
| 2004 | Complexity of Pseudoknot Prediction in Simple Models. Rune B. Lyngsø |
| 2004 | Coordination Mechanisms. George Christodoulou, Elias Koutsoupias, Akash Nanavati |
| 2004 | Counting in Trees for Free. Helmut Seidl, Thomas Schwentick, Anca Muscholl, Peter Habermehl |
| 2004 | Deciding Knowledge in Security Protocols Under Equational Theories. Martín Abadi, Véronique Cortier |
| 2004 | Definitions and Bounds for Self-Healing Key Distribution Schemes. Carlo Blundo, Paolo D'Arco, Alfredo De Santis |
| 2004 | Deterministic M2M Multicast in Radio Networks: (Extended Abstract). Leszek Gasieniec, Evangelos Kranakis, Andrzej Pelc, Qin Xin |
| 2004 | Dynamic Price Sequence and Incentive Compatibility (Extended Abstract). Ning Chen, Xiaotie Deng, Xiaoming Sun, Andrew Chi-Chih Yao |
| 2004 | Easily Refutable Subformulas of Large Random 3CNF Formulas. Uriel Feige, Eran Ofek |
| 2004 | Ecological Turing Machines. Bruno Durand, Andrei A. Muchnik, Maxim Ushakov, Nikolai K. Vereshchagin |
| 2004 | Efficient Computation of Equilibrium Prices for Markets with Leontief Utilities. Bruno Codenotti, Kasturi R. Varadarajan |
| 2004 | Efficient Consistency Proofs for Generalized Queries on a Committed Database. Rafail Ostrovsky, Charles Rackoff, Adam D. Smith |
| 2004 | Efficiently Computing Succinct Trade-Off Curves. Sergei Vassilvitskii, Mihalis Yannakakis |
| 2004 | Entropy as a Fixed Point. Keye Martin |
| 2004 | Exact (Exponential) Algorithms for Treewidth and Minimum Fill-In. Fedor V. Fomin, Dieter Kratsch, Ioan Todinca |
| 2004 | Exponential Lower Bounds for the Running Time of DPLL Algorithms on Satisfiable Formulas. Michael Alekhnovich, Edward A. Hirsch, Dmitry Itsykson |
| 2004 | Extensional Theories and Rewriting. Grigore Rosu |
| 2004 | External Memory Algorithms for Diameter and All-Pairs Shortest-Paths on Sparse Graphs. Lars Arge, Ulrich Meyer, Laura Toma |
| 2004 | Fairness to All While Downsizing. Bala Kalyanasundaram, Mahendran Velauthapillai |
| 2004 | Fast Parameterized Algorithms for Graphs on Surfaces: Linear Kernel and Exponential Speed-Up. Fedor V. Fomin, Dimitrios M. Thilikos |
| 2004 | Feasible Proofs and Computations: Partnership and Fusion. Alexander A. Razborov |
| 2004 | Further Improvements in Competitive Guarantees for QoS Buffering. Nikhil Bansal, Lisa Fleischer, Tracy Kimbrel, Mohammad Mahdian, Baruch Schieber, Maxim Sviridenko |
| 2004 | Games with Winning Conditions of High Borel Complexity. Olivier Serre |
| 2004 | Grammar Compression, LZ-Encodings, and String Algorithms with Implicit Input. Wojciech Rytter |
| 2004 | Greedy Regular Expression Matching. Alain Frisch, Luca Cardelli |
| 2004 | Group Spreading: A Protocol for Provably Secure Distributed Name Service. Baruch Awerbuch, Christian Scheideler |
| 2004 | Hardness of String Similarity Search and Other Indexing Problems. Süleyman Cenk Sahinalp, Andrey Utis |
| 2004 | Improved Results for Data Migration and Open Shop Scheduling. Rajiv Gandhi, Magnús M. Halldórsson, Guy Kortsarz, Hadas Shachnai |
| 2004 | Interactive Observability in Ludics. Claudia Faggian |
| 2004 | LA, Permutations, and the Hajós Calculus. Michael Soltys |
| 2004 | Learning a Hidden Subgraph. Noga Alon, Vera Asodi |
| 2004 | Linear Tolls Suffice: New Bounds and Algorithms for Tolls in Single Source Networks. Lisa Fleischer |
| 2004 | Linear and Branching Metrics for Quantitative Transition Systems. Luca de Alfaro, Marco Faella, Mariëlle Stoelinga |
| 2004 | Linear-Time List Decoding in Error-Free Settings: (Extended Abstract). Venkatesan Guruswami, Piotr Indyk |
| 2004 | Locally Consistent Constraint Satisfaction Problems: (Extended Abstract). Zdenek Dvorák, Daniel Král, Ondrej Pangrác |
| 2004 | Model Checking with Multi-valued Logics. Glenn Bruns, Patrice Godefroid |
| 2004 | Nash Equilibria in Discrete Routing Games with Convex Latency Functions. Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien, Manuel Rode |
| 2004 | On Graph Problems in a Semi-streaming Model. Joan Feigenbaum, Sampath Kannan, Andrew McGregor, Siddharth Suri, Jian Zhang |
| 2004 | On Randomization Versus Synchronization in Distributed Systems. Hagen Völzer |
| 2004 | On the Expressive Power of Monadic Least Fixed Point Logic. Nicole Schweikardt |
| 2004 | On the Power of Ambainis's Lower Bounds. Shengyu Zhang |
| 2004 | Online Scheduling of Equal-Length Jobs: Randomization and Restarts Help. Marek Chrobak, Wojciech Jawor, Jirí Sgall, Tomás Tichý |
| 2004 | Online Scheduling with Bounded Migration. Peter Sanders, Naveen Sivadasan, Martin Skutella |
| 2004 | Optimal Reachability for Weighted Timed Games. Rajeev Alur, Mikhail Bernadsky, P. Madhusudan |
| 2004 | Optimal Website Design with the Constrained Subtree Selection Problem. Brent Heeringa, Micah Adler |
| 2004 | Projecting Games on Hypercoherences. Pierre Boudes |
| 2004 | Property Testing of Regular Tree Languages. Frédéric Magniez, Michel de Rougemont |
| 2004 | Propositional PSPACE Reasoning with Boolean Programs Versus Quantified Boolean Formulas. Alan Skelley |
| 2004 | Quantum Query Complexity of Some Graph Problems. Christoph Dürr, Mark Heiligman, Peter Høyer, Mehdi Mhalla |
| 2004 | Regular Solutions of Language Inequalities and Well Quasi-orders. Michal Kunc |
| 2004 | Representing Nested Inductive Types Using W-Types. Michael Gordon Abbott, Thorsten Altenkirch, Neil Ghani |
| 2004 | Self-Adjusting Computation. Robert Harper |
| 2004 | Selfish Unsplittable Flows. Dimitris Fotakis, Spyros C. Kontogiannis, Paul G. Spirakis |
| 2004 | Simple Permutations Mix Well. Shlomo Hoory, Avner Magen, Steven A. Myers, Charles Rackoff |
| 2004 | Solving Two-Variable Word Equations (Extended Abstract). Robert Dabrowski, Wojciech Plandowski |
| 2004 | Some Results on Effective Randomness. Wolfgang Merkle, Nenad Mihailovic, Theodore A. Slaman |
| 2004 | Sublinear-Time Approximation for Clustering Via Random Sampling. Artur Czumaj, Christian Sohler |
| 2004 | Succinct Representations of Functions. J. Ian Munro, S. Srinivasa Rao |
| 2004 | Syntactic Control of Concurrency. Dan R. Ghica, Andrzej S. Murawski, C.-H. Luke Ong |
| 2004 | Testing Monotonicity over Graph Products. Shirley Halevy, Eyal Kushilevitz |
| 2004 | Testing, Optimizaton, and Games. Mihalis Yannakakis |
| 2004 | The Black-Box Complexity of Nearest Neighbor Search. Robert Krauthgamer, James R. Lee |
| 2004 | The Complexity of Equivariant Unification. James Cheney |
| 2004 | The Complexity of Partition Functions. Andrei A. Bulatov, Martin Grohe |
| 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 | The Minimum-Entropy Set Cover Problem. Eran Halperin, Richard M. Karp |
| 2004 | The Past, Present, and Future of Web Search Engines p. Monika Henzinger |
| 2004 | The Power of Verification for One-Parameter Agents. Vincenzo Auletta, Roberto De Prisco, Paolo Penna, Giuseppe Persiano |
| 2004 | Towards an Algebraic Theory of Typed Mobile Processes. Yuxin Deng, Davide Sangiorgi |
| 2004 | Transparent Long Proofs: A First PCP Theorem for NP Klaus Meer |
| 2004 | Tree-Walking Automata Cannot Be Determinized. Mikolaj Bojanczyk, Thomas Colcombet |
| 2004 | Universality in Quantum Computation. Emmanuel Jeandel |
| 2004 | Wavelength Assignment in Optical Networks with Fixed Fiber Capacity. Matthew Andrews, Lisa Zhang |
| 2004 | What Do Program Logics and Type Systems Have in Common? Martin Hofmann |
| 2004 | Word Problems on Compressed Words. Markus Lohrey |