| 2004 | Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. | Liam Roditty, Uri Zwick |
| 2004 | Multilinear-NC neq Multilinear-NC. | Ran Raz |
| 2004 | Maximum Matchings via Gaussian Elimination. | Marcin Mucha, Piotr Sankowski |
| 2004 | Shuffling by Semi-Random Transpositions. | Elchanan Mossel, Yuval Peres, Alistair Sinclair |
| 2004 | Quantum Weak Coin-Flipping with Bias of 0.192. | Carlos Mochon |
| 2004 | Worst-Case to Average-Case Reductions Based on Gaussian Measures. | Daniele Micciancio, Oded Regev |
| 2004 | Random Edge Can Be Exponential on Abstract Cubes. | Jir Matousek, Tibor Szab |
| 2004 | An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. | Lap Chi Lau |
| 2004 | Private Codes or Succinct Random Codes That Are (Almost) Perfect. | Michael Langberg |
| 2004 | A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions. | Amit Kumar, Yogish Sabharwal, Sandeep Sen |
| 2004 | Measured Descent: A New Embedding Method for Finite Metrics. | Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | Triangulation and Embedding Using Small Sets of Beacons. | Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler |
| 2004 | Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. | Hartmut Klauck, Robert Spalek, Ronald de Wolf |
| 2004 | Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? | Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell |
| 2004 | Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. | Subhash Khot |
| 2004 | Hardness of Approximating the Shortest Vector Problem in Lattices. | Subhash Khot |
| 2004 | Testing Polynomials over General Fields. | Tali Kaufman, Dana Ron |
| 2004 | Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. | George Karakostas, Stavros G. Kolliopoulos |
| 2004 | Testing Low-Degree Polynomials over Prime Fields. | Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman |
| 2004 | A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. | Kamal Jain |
| 2004 | On the Power of Discrete and of Lexicographic Helly-Type Theorems. | Nir Halman |
| 2004 | An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. | Anupam Gupta, R. Ravi, Amitabh Sinha |
| 2004 | trong Spatial Mixing for Lattice Graphs with Fewer Colours. | Leslie Ann Goldberg, Russell A. Martin, Mike Paterson |
| 2004 | Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. | Ariel Gabizon, Ran Raz, Ronen Shaltiel |
| 2004 | No Sorting? Better Searching! | Gianni Franceschini, Roberto Grossi |