| 2004 | Rational secret sharing and multiparty computation: extended abstract. | Joseph Y. Halpern, Vanessa Teague |
| 2004 | Better extractors for better codes? | Venkatesan Guruswami |
| 2004 | Boosted sampling: approximation algorithms for stochastic optimization. | Anupam Gupta, Martin Pl, R. Ravi, Amitabh Sinha |
| 2004 | Sharp thresholds For monotone properties in random geometric graphs. | Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari |
| 2004 | Auction algorithms for market equilibrium. | Rahul Garg, Sanjiv Kapoor |
| 2004 | Computing Nash equilibria for scheduling on restricted parallel links. | Martin Gairing, Thomas Lcking, Marios Mavronicolas, Burkhard Monien |
| 2004 | Finding paths and cycles of superpolylogarithmic length. | Harold N. Gabow |
| 2004 | The difficulty of testing for isomorphism against a graph that is given in advance. | Eldar Fischer |
| 2004 | Sorting and searching in the presence of memory faults (without redundancy). | Irene Finocchi, Giuseppe F. Italiano |
| 2004 | On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. | Uriel Feige |
| 2004 | The complexity of pure Nash equilibria. | Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar |
| 2004 | Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. | Michael Elkin |
| 2004 | A simple polynomial-time rescaling algorithm for solving linear programs. | John Dunagan, Santosh S. Vempala |
| 2004 | The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. | Nikhil R. Devanur |
| 2004 | Estimating the weight of metric minimum spanning trees in sublinear-time. | Artur Czumaj, Christian Sohler |
| 2004 | An approximate Knig's theorem for edge-coloring weighted bipartite graphs. | Jos R. Correa, Michel X. Goemans |
| 2004 | Dictionary matching and indexing with errors and don't cares. | Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein |
| 2004 | New hardness results for congestion minimization and machine scheduling. | Julia Chuzhoy, Joseph Naor |
| 2004 | Asymmetric k-center is log | Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor |
| 2004 | Collective asynchronous reading with polylogarithmic worst-case overhead. | Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman |
| 2004 | (Almost) tight bounds and existence theorems for confluent flows. | Jiangzhuo Chen, Robert D. Kleinberg, Lszl Lovsz, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta |
| 2004 | Linear FPT reductions and computational lower bounds. | Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia |
| 2004 | The all-or-nothing multicommodity flow problem. | Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2004 | Multi-processor scheduling to minimize flow time with epsilon resource augmentation. | Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar |
| 2004 | Counting complexity classes for numeric computations II: algebraic and semialgebraic sets. | Peter Brgisser, Felipe Cucker |