| 2004 | 0(sqrt (log n)) Approximation to SPARSEST CUT in Õ(n Sanjeev Arora, Elad Hazan, Satyen Kale |
| 2004 | 45th Symposium on Foundations of Computer Science, FOCS 2004, Rome, Italy, October 17-19, 2004, Proceedings |
| 2004 | A Polynomial Time Algorithm for Computing the Arrow-Debreu Market Equilibrium for Linear Utilities. Kamal Jain |
| 2004 | A Simple Linear Time (1+έ)-Approximation Algorithm for k-Means Clustering in Any Dimensions. Amit Kumar, Yogish Sabharwal, Sandeep Sen |
| 2004 | Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev |
| 2004 | Algebras with Polynomial Identities and Computing the Determinant. Steve Chien, Alistair Sinclair |
| 2004 | An Approximate Max-Steiner-Tree-Packing Min-Steiner-Cut Theorem. Lap Chi Lau |
| 2004 | An Edge in Time Saves Nine: LP Rounding Approximation Algorithms for Stochastic Network Design. Anupam Gupta, R. Ravi, Amitabh Sinha |
| 2004 | An Optimal Randomised Cell Probe Lower Bound for Approximate Nearest Neighbour Searching. Amit Chakrabarti, Oded Regev |
| 2004 | An Unconditional Study of Computational Zero Knowledge. Salil P. Vadhan |
| 2004 | Approximating Edit Distance Efficiently. Ziv Bar-Yossef, T. S. Jayram, Robert Krauthgamer, Ravi Kumar |
| 2004 | Approximating the Stochastic Knapsack Problem: The Benefit of Adaptivity. Brian C. Dean, Michel X. Goemans, Jan Vondrák |
| 2004 | Assignment Testers: Towards a Combinatorial Proof of the PCP-Theorem. Irit Dinur, Omer Reingold |
| 2004 | Constructing Expander Graphs by 2-Lifts and Discrepancy vs. Spectral Gap. Yonatan Bilu, Nathan Linial |
| 2004 | Cryptography in NC Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
| 2004 | Deterministic Extractors for Bit-Fixing Sources by Obtaining an Independent Seed. Ariel Gabizon, Ran Raz, Ronen Shaltiel |
| 2004 | Dynamic Approximate All-Pairs Shortest Paths in Undirected Graphs. Liam Roditty, Uri Zwick |
| 2004 | Dynamic Optimality - Almost. Erik D. Demaine, Dion Harmon, John Iacono, Mihai Patrascu |
| 2004 | Dynamic Speed Scaling to Manage Energy and Temperature. Nikhil Bansal, Tracy Kimbrel, Kirk Pruhs |
| 2004 | Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). Piotr Sankowski |
| 2004 | Edge Pricing of Multicommodity Networks for Heterogeneous Selfish Users. George Karakostas, Stavros G. Kolliopoulos |
| 2004 | Edge-Disjoint Paths in Planar Graphs. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2004 | Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. Rahul Savani, Bernhard von Stengel |
| 2004 | Extracting Randomness Using Few Independent Sources. Boaz Barak, Russell Impagliazzo, Avi Wigderson |
| 2004 | Hardness of Approximating the Shortest Vector Problem in Lattices. Subhash Khot |
| 2004 | Hardness of Buy-at-Bulk Network Design. Matthew Andrews |
| 2004 | Hierarchy Theorems for Probabilistic Polynomial Time. Lance Fortnow, Rahul Santhanam |
| 2004 | Holographic Algorithms (Extended Abstract). Leslie G. Valiant |
| 2004 | Lattice Problems in NP cap coNP. Dorit Aharonov, Oded Regev |
| 2004 | Learnability and Automatizability. Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi |
| 2004 | Learning with Errors in Answers to Membership Queries. Laurence Bisht, Nader H. Bshouty, Lawrance Khoury |
| 2004 | Machine Minimization for Scheduling Jobs with Interval Constraints. Julia Chuzhoy, Sudipto Guha, Sanjeev Khanna, Joseph Naor |
| 2004 | Maximizing Quadratic Programs: Extending Grothendieck's Inequality. Moses Charikar, Anthony Wirth |
| 2004 | Maximum Matchings via Gaussian Elimination. Marcin Mucha, Piotr Sankowski |
| 2004 | Measured Descent: A New Embedding Method for Finite Metrics. Robert Krauthgamer, James R. Lee, Manor Mendel, Assaf Naor |
| 2004 | Multilinear-NC neq Multilinear-NC. Ran Raz |
| 2004 | No Sorting? Better Searching! Gianni Franceschini, Roberto Grossi |
| 2004 | On the (Im)possibility of Cryptography with Imperfect Randomness. Yevgeniy Dodis, Shien Jin Ong, Manoj Prabhakaran, Amit Sahai |
| 2004 | On the Integrality Ratio for Asymmetric TSP. Moses Charikar, Michel X. Goemans, Howard J. Karloff |
| 2004 | On the List and Bounded Distance Decodibility of the Reed-Solomon Codes (Extended Abstract). Qi Cheng, Daqing Wan |
| 2004 | On the Power of Discrete and of Lexicographic Helly-Type Theorems. Nir Halman |
| 2004 | On the Streaming Model Augmented with a Sorting Primitive. Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl |
| 2004 | Optimal Inapproximability Results for Max-Cut and Other 2-Variable CSPs? Subhash Khot, Guy Kindler, Elchanan Mossel, Ryan O'Donnell |
| 2004 | Optimal Power-Down Strategies. John Augustine, Sandy Irani, Chaitanya Swamy |
| 2004 | Private Codes or Succinct Random Codes That Are (Almost) Perfect. Michael Langberg |
| 2004 | Quantum Speed-Up of Markov Chain Based Algorithms. Mario Szegedy |
| 2004 | Quantum Walk Algorithm for Element Distinctness. Andris Ambainis |
| 2004 | Quantum Weak Coin-Flipping with Bias of 0.192. Carlos Mochon |
| 2004 | Quantum and Classical Strong Direct Product Theorems and Optimal Time-Space Tradeoffs. Hartmut Klauck, Robert Spalek, Ronald de Wolf |
| 2004 | Random Edge Can Be Exponential on Abstract Cubes. Jirí Matousek, Tibor Szabó |
| 2004 | Randomly Coloring Constant Degree Graphs. Martin E. Dyer, Alan M. Frieze, Thomas P. Hayes, Eric Vigoda |
| 2004 | Ruling Out PTAS for Graph Min-Bisection, Densest Subgraph and Bipartite Clique. Subhash Khot |
| 2004 | Shuffling by Semi-Random Transpositions. Elchanan Mossel, Yuval Peres, Alistair Sinclair |
| 2004 | Spectral Analysis of Random Graphs with Skewed Degree Distributions. Anirban Dasgupta, John E. Hopcroft, Frank McSherry |
| 2004 | Stochastic Optimization is (Almost) as easy as Deterministic Optimization. David B. Shmoys, Chaitanya Swamy |
| 2004 | Testing Low-Degree Polynomials over Prime Fields. Charanjit S. Jutla, Anindya C. Patthak, Atri Rudra, David Zuckerman |
| 2004 | Testing Polynomials over General Fields. Tali Kaufman, Dana Ron |
| 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 | The Price of Stability for Network Design with Fair Cost Allocation. Elliot Anshelevich, Anirban Dasgupta, Jon M. Kleinberg, Éva Tardos, Tom Wexler, Tim Roughgarden |
| 2004 | Tolls for Heterogeneous Selfish Users in Multicommodity Networks and Generalized Congestion Games. Lisa Fleischer, Kamal Jain, Mohammad Mahdian |
| 2004 | Triangulation and Embedding Using Small Sets of Beacons. Jon M. Kleinberg, Aleksandrs Slivkins, Tom Wexler |
| 2004 | Universally Composable Protocols with Relaxed Set-Up Assumptions. Boaz Barak, Ran Canetti, Jesper Buus Nielsen, Rafael Pass |
| 2004 | Worst-Case to Average-Case Reductions Based on Gaussian Measures. Daniele Micciancio, Oded Regev |
| 2004 | trong Spatial Mixing for Lattice Graphs with Fewer Colours. Leslie Ann Goldberg, Russell A. Martin, Mike Paterson |