| 2004 | The Bloomier filter: an efficient data structure for static support lookup tables. | Bernard Chazelle, Joe Kilian, Ronitt Rubinfeld, Ayellet Tal |
| 2004 | Who says you have to look at the input? The brave new world of sublinear computing. | Bernard Chazelle |
| 2004 | Quantitative stochastic parity games. | Krishnendu Chatterjee, Marcin Jurdzinski, Thomas A. Henzinger |
| 2004 | Non-migratory online deadline scheduling on multiprocessors. | Ho-Leung Chan, Tak Wah Lam, Kar-Keung To |
| 2004 | An optimal randomized algorithm for maximum Tukey depth. | Timothy M. Chan |
| 2004 | A deterministic near-linear time algorithm for finding minimum cuts in planar graphs. | Parinya Chalermsook, Jittat Fakcharoenphol, Danupon Nanongkai |
| 2004 | The list partition problem for graphs. | Kathie Cameron, Elaine M. Eschen, Chnh T. Hong, R. Sritharan |
| 2004 | Competitive analysis of organization networks or multicast acknowledgement: how much to wait? | Carlos Brito, Elias Koutsoupias, Shailesh Vaya |
| 2004 | A new algorithm for normal dominance constraints. | Manuel Bodirsky, Denys Duchier, Joachim Niehren, Sebastian Miele |
| 2004 | Approximate budget balanced mechanisms with low communication costs for the multicast cost-sharing problem. | Markus Blser |
| 2004 | Compact representations of ordered sets. | Daniel K. Blandford, Guy E. Blelloch |
| 2004 | Torpid mixing of simulated tempering on the Potts model. | Nayantara Bhatnagar, Dana Randall |
| 2004 | Two tricks to triangulate chordal probe graphs in polynomial time. | Anne Berry, Martin Charles Golumbic, Marina Lipshteyn |
| 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 | Probabilistic analysis of knapsack core algorithms. | Ren Beier, Berthold Vcking |
| 2004 | Computing equilibria for congestion games with (im)perfect information. | Ren Beier, Artur Czumaj, Piotr Krysta, Berthold Vcking |
| 2004 | Reconstructing strings from random traces. | Tugkan Batu, Sampath Kannan, Sanjeev Khanna, Andrew McGregor |
| 2004 | Approximate distance oracles for unweighted graphs in (n | Surender Baswana, Sandeep Sen |
| 2004 | Lyndon words with a fixed standard right factor. | Frdrique Bassino, Julien Clment, Cyril Nicaud |
| 2004 | Randomized | Yair Bartal, Manor Mendel |
| 2004 | Dimension reduction for ultrametrics. | Yair Bartal, Manor Mendel |
| 2004 | Windows scheduling as a restricted version of Bin Packing. | Amotz Bar-Noy, Richard E. Ladner, Tami Tamir |
| 2004 | New approximability and inapproximability results for 2-dimensional Bin Packing. | Nikhil Bansal, Maxim Sviridenko |
| 2004 | On minimizing the total flow time on multiple machines. | Nikhil Bansal |
| 2004 | Almost-Delaunay simplices: nearest neighbor relations for imprecise points. | Deepak Bandyopadhyay, Jack Snoeyink |