| 2004 | Hierarchy Theorems for Probabilistic Polynomial Time. | Lance Fortnow, Rahul Santhanam |
| 2004 | Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. | Lisa Fleischer, Kamal Jain, Mohammad Mahdian |
| 2004 | Randomly Coloring Constant Degree Graphs. | Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda |
| 2004 | On the (Im)possibility of Cryptography with Imperfect Randomness. | Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai |
| 2004 | Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. | Irit Dinur, Omer Reingold |
| 2004 | Dynamic Optimality - Almost. | Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu |
| 2004 | Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. | Brian C. Dean, Michel X. Goemans, Jan Vondrk |
| 2004 | Spectral Analysis of Random Graphs with Skewed Degree Distributions. | Anirban Dasgupta, John E. Hopcroft, Frank McSherry |
| 2004 | The Exact Satisfiability Threshold for a Potentially Intractible Random Constraint Satisfaction Problem. | Harold S. Connamacher, Michael Molloy |
| 2004 | The Hardness of Metric Labeling. | Julia Chuzhoy, Joseph Naor |
| 2004 | Machine Minimization for Scheduling Jobs with Interval Constraints. | Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor |
| 2004 | Algebras with Polynomial Identities and Computing the Determinant. | Steve Chien, Alistair Sinclair |
| 2004 | On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract). | Qi Cheng, Daqing Wan |
| 2004 | Edge-Disjoint Paths in Planar Graphs. | Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2004 | Maximizing Quadratic Programs: Extending Grothendieck's Inequality. | Moses Charikar, Anthony Wirth |
| 2004 | On the Integrality Ratio for Asymmetric TSP. | Moses Charikar, Michel X. Goemans, Howard J. Karloff |
| 2004 | An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. | Amit Chakrabarti, Oded Regev |
| 2004 | Learning with Errors in Answers to Membership Queries. | Laurence Bisht, Nader H. Bshouty, Lawrance Khoury |
| 2004 | Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. | Yonatan Bilu, Nathan Linial |
| 2004 | Extracting Randomness Using Few Independent Sources. | Boaz Barak, Russell Impagliazzo, Avi Wigderson |
| 2004 | Universally Composable Protocols with Relaxed Set-Up Assumptions. | Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass |
| 2004 | Approximating Edit Distance Efficiently. | Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar |
| 2004 | Dynamic Speed Scaling to Manage Energy and Temperature. | Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs |
| 2004 | Optimal Power-Down Strategies. | John Augustine, Sandy Irani, Chaitanya Swamy |
| 2004 | 0(sqrt (log n)) Approximation to SPARSEST CUT in (n | Sanjeev Arora, Elad Hazan, Satyen Kale |