| 2004 | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. | Daniel A. Spielman, Shang-Hua Teng |
| 2004 | Derandomizing homomorphism testing in general groups. | Amir Shpilka, Avi Wigderson |
| 2004 | Quantum and classical query complexities of local search are polynomially related. | Miklos Santha, Mario Szegedy |
| 2004 | A new family of Cayley expanders (?). | Eyal Rozenman, Aner Shalev, Avi Wigderson |
| 2004 | A fully dynamic reachability algorithm for directed graphs with an almost linear update time. | Liam Roditty, Uri Zwick |
| 2004 | The quantum adiabatic optimization algorithm and local minima. | Ben Reichardt |
| 2004 | Multi-linear formulas for permanent and determinant are of super-polynomial size. | Ran Raz |
| 2004 | New notions of security: achieving universal composability without trusted setup. | Manoj Prabhakaran, Amit Sahai |
| 2004 | Lower bounds for dynamic connectivity. | Mihai Patrascu, Erik D. Demaine |
| 2004 | Bounded-concurrent secure multi-party computation with a dishonest majority. | Rafael Pass |
| 2004 | Approximate max-integral-flow/min-multicut theorems. | Kenji Obata |
| 2004 | Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks. | Gurmeet Singh Manku, Moni Naor, Udi Wieder |
| 2004 | Hit-and-run from a corner. | Lszl Lovsz, Santosh S. Vempala |
| 2004 | Primal-dual algorithms for deterministic inventory problems. | Retsef Levi, Robin Roundy, David B. Shmoys |
| 2004 | Approximation algorithm for k-node connected subgraphs via critical graphs. | Guy Kortsarz, Zeev Nutov |
| 2004 | Using mixture models for collaborative filtering. | Jon M. Kleinberg, Mark Sandler |
| 2004 | Low distortion maps between point sets. | Claire Kenyon, Yuval Rabani, Alistair Sinclair |
| 2004 | A decentralized algorithm for spectral analysis. | David Kempe, Frank McSherry |
| 2004 | Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. | Jonathan A. Kelner |
| 2004 | Batch codes and their applications. | Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2004 | Algorithms for dynamic geometric problems over data streams. | Piotr Indyk |
| 2004 | A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. | Jonas Holmerin, Subhash Khot |
| 2004 | Using nondeterminism to amplify hardness. | Alexander Healy, Salil P. Vadhan, Emanuele Viola |
| 2004 | Completeness in two-party secure computation: a computational view. | Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen |
| 2004 | On coresets for k-means and k-median clustering. | Sariel Har-Peled, Soham Mazumdar |