| 2004 | A certifying algorithm for the consecutive-ones property. Ross M. McConnell |
| 2004 | A characterization of easily testable induced subgraphs. Noga Alon, Asaf Shapira |
| 2004 | A determinant-based algorithm for counting perfect matchings in a general graph. Steve Chien |
| 2004 | A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai |
| 2004 | A fast approximation scheme for fractional covering problems with variable upper bounds. Lisa Fleischer |
| 2004 | A faster distributed protocol for constructing a minimum spanning tree. Michael Elkin |
| 2004 | A general approach to online network optimization problems. Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor |
| 2004 | A maiden analysis of Longest Wait First. Jeff Edmonds, Kirk Pruhs |
| 2004 | A new algorithm for normal dominance constraints. Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele |
| 2004 | A note on the nearest neighbor in growth-restricted metrics. Kirsten Hildrum, John Kubiatowicz, Sean Ma, Satish Rao |
| 2004 | A stronger bound on Braess's Paradox. Henry C. Lin, Tim Roughgarden, Éva Tardos |
| 2004 | A time efficient Delaunay refinement algorithm. Gary L. Miller |
| 2004 | Adaptive sampling for quickselect. Conrado Martinez, Daniel Panario, Alfredo Viola |
| 2004 | Algorithms for infinite huffman-codes. Mordecai J. Golin, Kin Keung Ma |
| 2004 | Almost-Delaunay simplices: nearest neighbor relations for imprecise points. Deepak Bandyopadhyay, Jack Snoeyink |
| 2004 | An exact subexponential-time lattice algorithm for Asian options. Tian-Shyr Dai, Yuh-Dauh Lyuu |
| 2004 | An improved data stream algorithm for frequency moments. Don Coppersmith, Ravi Kumar |
| 2004 | An optimal randomized algorithm for maximum Tukey depth. Timothy M. Chan |
| 2004 | Approximate Nearest Neighbor under edit distance via product metrics. Piotr Indyk |
| 2004 | Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem. Markus Bläser |
| 2004 | Approximate classification via earthmover metrics. Aaron Archer, Jittat Fakcharoenphol, Chris Harrelson, Robert Krauthgamer, Kunal Talwar, Éva Tardos |
| 2004 | Approximate distance oracles for unweighted graphs in Õ(n Surender Baswana, Sandeep Sen |
| 2004 | Approximate local search in combinatorial optimization. James B. Orlin, Abraham P. Punnen, Andreas S. Schulz |
| 2004 | Approximating Minimum Max-Stretch spanning Trees on unweighted graphs. Yuval Emek, David Peleg |
| 2004 | Approximating the two-level facility location problem via a quasi-greedy approach. Jiawei Zhang |
| 2004 | Approximation schemes for Metric Bisection and partitioning. Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon |
| 2004 | Approximation schemes for minimum 2-edge-connected and biconnected subgraphs in planar graphs. Artur Czumaj, Michelangelo Grigni, Papa A. Sissokho, Hairong Zhao |
| 2004 | Approximation schemes for multidimensional packing. José R. Correa, Claire Kenyon |
| 2004 | Bipartite roots of graphs. Lap Chi Lau |
| 2004 | Buffer minimization using max-coloring. Sriram V. Pemmaraju, Rajiv Raman, Kasturi R. Varadarajan |
| 2004 | Caching queues in memory buffers. Rajeev Motwani, Dilys Thomas |
| 2004 | Compact representations of ordered sets. Daniel K. Blandford, Guy E. Blelloch |
| 2004 | Competitive analysis of organization networks or multicast acknowledgement: how much to wait? Carlos Brito, Elias Koutsoupias, Shailesh Vaya |
| 2004 | Complexities for generalized models of self-assembly. Gagan Aggarwal, Michael H. Goldwasser, Ming-Yang Kao, Robert T. Schweller |
| 2004 | Complexity classification of network information flow problems. April Rasala Lehman, Eric Lehman |
| 2004 | Compression boosting in optimal linear time using the Burrows-Wheeler Transform. Paolo Ferragina, Giovanni Manzini |
| 2004 | Computing equilibria for congestion games with (im)perfect information. René Beier, Artur Czumaj, Piotr Krysta, Berthold Vöcking |
| 2004 | Computing maximally separated sets in the plane and independent sets in the intersection graph of unit disks. Pankaj K. Agarwal, Mark H. Overmars, Micha Sharir |
| 2004 | Constructing finite field extensions with large order elements. Qi Cheng |
| 2004 | Correlation Clustering: maximizing agreements via semidefinite programming. Chaitanya Swamy |
| 2004 | Covering minimum spanning trees of random subgraphs. Michel X. Goemans, Jan Vondrák |
| 2004 | Detecting short directed cycles using rectangular matrix multiplication and dynamic programming. Raphael Yuster, Uri Zwick |
| 2004 | Dimension reduction for ultrametrics. Yair Bartal, Manor Mendel |
| 2004 | Dynamizing static algorithms, with applications to dynamic trees and history independence. Umut A. Acar, Guy E. Blelloch, Robert Harper, Jorge L. Vittes, Shan Leung Maverick Woo |
| 2004 | Efficient algorithms for bichromatic separability. Pankaj K. Agarwal, Boris Aronov, Vladlen Koltun |
| 2004 | Efficient estimation algorithms for neighborhood variance and other moments. Edith Cohen, Haim Kaplan |
| 2004 | Efficiently decodable codes meeting Gilbert-Varshamov bound for low rates. Venkatesan Guruswami, Piotr Indyk |
| 2004 | End-to-end packet-scheduling in wireless ad-hoc networks. V. S. Anil Kumar, Madhav V. Marathe, Srinivasan Parthasarathy, Aravind Srinivasan |
| 2004 | Equivalence of local treewidth and linear local treewidth and its algorithmic applications. Erik D. Demaine, Mohammad Taghi Hajiaghayi |
| 2004 | Experimental analysis of dynamic all pairs shortest path algorithms. Camil Demetrescu, Stefano Emiliozzi, Giuseppe F. Italiano |
| 2004 | Exponential bounds for DPLL below the satisfiability threshold. Dimitris Achlioptas, Paul Beame, Michael Molloy |
| 2004 | Facility location with Service Installation Costs. David B. Shmoys, Chaitanya Swamy, Retsef Levi |
| 2004 | Fair and efficient router congestion control. Xiaojie Gao, Kamal Jain, Leonard J. Schulman |
| 2004 | Family trees: an ordered dictionary with optimal congestion, locality, degree, and search time. Kevin C. Zatloukal, Nicholas J. A. Harvey |
| 2004 | Fast approximate pattern matching with few indels via embeddings. Mihai Badoiu, Piotr Indyk |
| 2004 | Fast mixing for independent sets, colorings and other models on trees. Fabio Martinelli, Alistair Sinclair, Dror Weitz |
| 2004 | Fault-tolerant gathering algorithms for autonomous mobile robots. Noa Agmon, David Peleg |
| 2004 | Finding a long directed cycle. Harold N. Gabow, Shuxin Nie |
| 2004 | Finding dominators revisited: extended abstract. Loukas Georgiadis, Robert Endre Tarjan |
| 2004 | Frugality in path auctions. Edith Elkind, Amit Sahai, Kenneth Steiglitz |
| 2004 | Generic quantum Fourier transforms. Cristopher Moore, Daniel N. Rockmore, Alexander Russell |
| 2004 | Graph decomposition and a greedy algorithm for edge-disjoint paths. Kasturi R. Varadarajan, Ganesh Venkataraman |
| 2004 | Hole and antihole detection in graphs. Stavros D. Nikolopoulos, Leonidas Palios |
| 2004 | How random is the human genome? Peter Winkler |
| 2004 | Improved bounds on sorting with length-weighted reversals. Michael A. Bender, Dongdong Ge, Simai He, Haodong Hu, Ron Y. Pinter, Steven Skiena, Firas Swidan |
| 2004 | Improved upper bounds for 3-SAT. Kazuo Iwama, Suguru Tamaki |
| 2004 | Interpolation search for non-independent data. Erik D. Demaine, Thouis R. Jones, Mihai Patrascu |
| 2004 | Invadable self-assembly: combining robustness with efficiency. Ho-Lin Chen, Qi Cheng, Ashish Goel, Ming-Deh A. Huang, Pablo Moisset de Espanés |
| 2004 | LAND: stretch (1 + epsilon) locality-aware networks for DHTs. Ittai Abraham, Dahlia Malkhi, Oren Dobzinski |
| 2004 | Linear phase transition in random linear constraint satisfaction problems. David Gamarnik |
| 2004 | Locally satisfiable formulas. Daniel Král |
| 2004 | Lyndon words with a fixed standard right factor. Frédérique Bassino, Julien Clément, Cyril Nicaud |
| 2004 | Matrix rounding and approximation. Benjamin Doerr |
| 2004 | Meldable RAM priority queues and minimum directed spanning trees. Ran Mendelson, Mikkel Thorup, Uri Zwick |
| 2004 | Minimizing migrations in fair multiprocessor scheduling of persistent tasks. Tracy Kimbrel, Baruch Schieber, Maxim Sviridenko |
| 2004 | Minimizing the stabbing number of matchings, trees, and triangulations. Sándor P. Fekete, Marco E. Lübbecke, Henk Meijer |
| 2004 | Minimum moment Steiner trees. Wangqi Qiu, Weiping Shi |
| 2004 | Models of greedy algorithms for graph problems. Sashka Davis, Russell Impagliazzo |
| 2004 | Multicommodity facility location. R. Ravi, Amitabh Sinha |
| 2004 | Navigating nets: simple algorithms for proximity search. Robert Krauthgamer, James R. Lee |
| 2004 | Network failure detection and graph connectivity. Jon M. Kleinberg, Mark Sandler, Aleksandrs Slivkins |
| 2004 | New approximability and inapproximability results for 2-dimensional Bin Packing. Nikhil Bansal, Maxim Sviridenko |
| 2004 | Non-migratory online deadline scheduling on multiprocessors. Ho-Leung Chan, Tak Wah Lam, Kar-Keung To |
| 2004 | On broadcasting in heterogenous networks. Samir Khuller, Yoo Ah Kim |
| 2004 | On colorings of squares of outerplanar graphs. Geir Agnarsson, Magnús M. Halldórsson |
| 2004 | On contract-and-refine transformations between phylogenetic trees. Ganeshkumar Ganapathy, Vijaya Ramachandran, Tandy J. Warnow |
| 2004 | On distributions computable by random walks on graphs. Guy Kindler, Dan Romik |
| 2004 | On finding a guard that sees most and a shop that sells most. Otfried Cheong, Alon Efrat, Sariel Har-Peled |
| 2004 | On minimizing the total flow time on multiple machines. Nikhil Bansal |
| 2004 | On rectangle packing: maximizing benefits. Klaus Jansen, Guochuan Zhang |
| 2004 | On the convergence time of a path-vector protocol. Howard J. Karloff |
| 2004 | On the costs and benefits of procrastination: approximation algorithms for stochastic combinatorial optimization problems. Nicole Immorlica, David R. Karger, Maria Minkoff, Vahab S. Mirrokni |
| 2004 | On the diameter of the symmetric group: polynomial bounds. László Babai, Robert Beals, Ákos Seress |
| 2004 | On the number of rectangular partitions. Eyal Ackerman, Gill Barequet, Ron Y. Pinter |
| 2004 | Optimal online bounded space multidimensional packing. Leah Epstein, Rob van Stee |
| 2004 | Optimal routing in Chord. Prasanna Ganesan, Gurmeet Singh Manku |
| 2004 | Optimal space lower bounds for all frequency moments. David P. Woodruff |
| 2004 | Optimally scheduling video-on-demand to minimize delay when server and receiver bandwidth may differ. William S. Evans, David G. Kirkpatrick |
| 2004 | Output-sensitive construction of the union of triangles. Eti Ezra, Micha Sharir |
| 2004 | Point containment in the integer hull of a polyhedron. Ernst Althaus, Friedrich Eisenbrand, Stefan Funke, Kurt Mehlhorn |
| 2004 | Polynomial interpolation from multiples. Joachim von zur Gathen, Igor E. Shparlinski |
| 2004 | Probabilistic analysis of knapsack core algorithms. René Beier, Berthold Vöcking |
| 2004 | Proceedings of the Fifteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2004, New Orleans, Louisiana, USA, January 11-14, 2004 J. Ian Munro |
| 2004 | Proximity Mergesort: optimal in-place sorting in the cache-oblivious model. Gianni Franceschini |
| 2004 | Quantitative stochastic parity games. Krishnendu Chatterjee, Marcin Jurdzinski, Thomas A. Henzinger |
| 2004 | Quantum computing. Raymond Laflamme |
| 2004 | Quasiconvex analysis of backtracking algorithms. David Eppstein |
| 2004 | Randomized Yair Bartal, Manor Mendel |
| 2004 | Randomized pursuit-evasion with limited visibility. Volkan Isler, Sampath Kannan, Sanjeev Khanna |
| 2004 | Rank-maximal matchings. Robert W. Irving, Telikepalli Kavitha, Kurt Mehlhorn, Dimitrios Michail, Katarzyna E. Paluch |
| 2004 | Reconstructing strings from random traces. Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor |
| 2004 | Retroactive data structures. Erik D. Demaine, John Iacono, Stefan Langerman |
| 2004 | Routing and scheduling in multihop wireless networks with time-varying channels. Matthew Andrews, Lisa Zhang |
| 2004 | SRPT optimally utilizes faster machines to minimize flow time. Jason McCullough, Eric Torng |
| 2004 | Simultaneous diophantine approximation with excluded primes. László Babai, Daniel Stefankovic |
| 2004 | Slow mixing of Glauber dynamics for the hard-core model on the hypercube. David J. Galvin, Prasad Tetali |
| 2004 | Special edges, and approximating the smallest directed Harold N. Gabow |
| 2004 | Structural and algorithmic aspects of massive social networks. Stephen G. Eubank, V. S. Anil Kumar, Madhav V. Marathe, Aravind Srinivasan, Nan Wang |
| 2004 | Subexponential parameterized algorithms on graphs of bounded-genus and Erik D. Demaine, Fedor V. Fomin, Mohammad Taghi Hajiaghayi, Dimitrios M. Thilikos |
| 2004 | Succinct ordinal trees with level-ancestor queries. Richard F. Geary, Rajeev Raman, Venkatesh Raman |
| 2004 | Tabulation based 4-universal hashing with applications to second moment estimation. Mikkel Thorup, Yin Zhang |
| 2004 | Testing bipartiteness of geometric intersection graphs. David Eppstein |
| 2004 | The Bloomier filter: an efficient data structure for static support lookup tables. Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal |
| 2004 | The directed circular arrangement problem. Joseph Naor, Roy Schwartz |
| 2004 | The hyperring: a low-congestion deterministic data structure for distributed environments. Baruch Awerbuch, Christian Scheideler |
| 2004 | The list partition problem for graphs. Kathie Cameron, Elaine M. Eschen, Chính T. Hoàng, R. Sritharan |
| 2004 | The maximum latency of selfish routing. Tim Roughgarden |
| 2004 | The number of bit comparisons used by Quicksort: an average-case analysis. James Allen Fill, Svante Janson |
| 2004 | The power of basis selection in fourier sampling: hidden subgroup problems in affine groups. Cristopher Moore, Daniel N. Rockmore, Alexander Russell, Leonard J. Schulman |
| 2004 | The pure literal rule threshold and cores in random hypergraphs. Michael Molloy |
| 2004 | The wake-up problem in multi-hop radio networks. Marek Chrobak, Leszek Gasieniec, Dariusz R. Kowalski |
| 2004 | Tight bounds for the partial-sums problem. Mihai Patrascu, Erik D. Demaine |
| 2004 | Torpid mixing of simulated tempering on the Potts model. Nayantara Bhatnagar, Dana Randall |
| 2004 | Trade-offs on the location of the core node in a network. Jean-François Macq, Michel X. Goemans |
| 2004 | Two tricks to triangulate chordal probe graphs in polynomial time. Anne Berry, Martin Charles Golumbic, Marina Lipshteyn |
| 2004 | Variable length path coupling. Thomas P. Hayes, Eric Vigoda |
| 2004 | When indexing equals compression: experiments with compressing suffix arrays and applications. Roberto Grossi, Ankur Gupta, Jeffrey Scott Vitter |
| 2004 | Who says you have to look at the input? The brave new world of sublinear computing. Bernard Chazelle |
| 2004 | Windows scheduling as a restricted version of Bin Packing. Amotz Bar-Noy, Richard E. Ladner, Tami Tamir |