| 2004 | (Almost) tight bounds and existence theorems for confluent flows. Jiangzhuo Chen, Robert D. Kleinberg, László Lovász, Rajmohan Rajaraman, Ravi Sundaram, Adrian Vetta |
| 2004 | A conjecture about polynomial time computable lattice-lattice functions. Miklós Ajtai |
| 2004 | A decentralized algorithm for spectral analysis. David Kempe, Frank McSherry |
| 2004 | A fully dynamic reachability algorithm for directed graphs with an almost linear update time. Liam Roditty, Uri Zwick |
| 2004 | A new PCP outer verifier with applications to homogeneous linear equations and max-bisection. Jonas Holmerin, Subhash Khot |
| 2004 | A new family of Cayley expanders (?). Eyal Rozenman, Aner Shalev, Avi Wigderson |
| 2004 | A simple polynomial-time rescaling algorithm for solving linear programs. John Dunagan, Santosh S. Vempala |
| 2004 | Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. Baruch Awerbuch, Robert D. Kleinberg |
| 2004 | Algorithms for dynamic geometric problems over data streams. Piotr Indyk |
| 2004 | An approximate König's theorem for edge-coloring weighted bipartite graphs. José R. Correa, Michel X. Goemans |
| 2004 | Approximate max-integral-flow/min-multicut theorems. Kenji Obata |
| 2004 | Approximating the cut-norm via Grothendieck's inequality. Noga Alon, Assaf Naor |
| 2004 | Approximation algorithm for k-node connected subgraphs via critical graphs. Guy Kortsarz, Zeev Nutov |
| 2004 | Approximation algorithms for deadline-TSP and vehicle routing with time-windows. Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson |
| 2004 | Asymmetric k-center is log Julia Chuzhoy, Sudipto Guha, Eran Halperin, Sanjeev Khanna, Guy Kortsarz, Joseph Naor |
| 2004 | Auction algorithms for market equilibrium. Rahul Garg, Sanjiv Kapoor |
| 2004 | Batch codes and their applications. Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2004 | Better extractors for better codes? Venkatesan Guruswami |
| 2004 | Boosted sampling: approximation algorithms for stochastic optimization. Anupam Gupta, Martin Pál, R. Ravi, Amitabh Sinha |
| 2004 | Bounded-concurrent secure multi-party computation with a dishonest majority. Rafael Pass |
| 2004 | Bypassing the embedding: algorithms for low dimensional metrics. Kunal Talwar |
| 2004 | Collective asynchronous reading with polylogarithmic worst-case overhead. Bogdan S. Chlebus, Dariusz R. Kowalski, Alexander A. Shvartsman |
| 2004 | Completeness in two-party secure computation: a computational view. Danny Harnik, Moni Naor, Omer Reingold, Alon Rosen |
| 2004 | Computing Nash equilibria for scheduling on restricted parallel links. Martin Gairing, Thomas Lücking, Marios Mavronicolas, Burkhard Monien |
| 2004 | Counting complexity classes for numeric computations II: algebraic and semialgebraic sets. Peter Bürgisser, Felipe Cucker |
| 2004 | Depth through breadth, or why should we attend talks in other areas? Avi Wigderson |
| 2004 | Derandomizing homomorphism testing in general groups. Amir Shpilka, Avi Wigderson |
| 2004 | Dictionary matching and indexing with errors and don't cares. Richard Cole, Lee-Ad Gottlieb, Moshe Lewenstein |
| 2004 | Estimating the weight of metric minimum spanning trees in sublinear-time. Artur Czumaj, Christian Sohler |
| 2004 | Expander flows, geometric embeddings and graph partitioning. Sanjeev Arora, Satish Rao, Umesh V. Vazirani |
| 2004 | Exponential separation of quantum and classical one-way communication complexity. Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis |
| 2004 | Finding paths and cycles of superpolylogarithmic length. Harold N. Gabow |
| 2004 | Graph entropy and quantum sorting problems. Andrew Chi-Chih Yao |
| 2004 | Hit-and-run from a corner. László Lovász, Santosh S. Vempala |
| 2004 | Isotopic implicit surface meshing. Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter |
| 2004 | Know thy neighbor's neighbor: the power of lookahead in randomized P2P networks. Gurmeet Singh Manku, Moni Naor, Udi Wieder |
| 2004 | Linear FPT reductions and computational lower bounds. Jianer Chen, Xiuzhen Huang, Iyad A. Kanj, Ge Xia |
| 2004 | Low distortion maps between point sets. Claire Kenyon, Yuval Rabani, Alistair Sinclair |
| 2004 | Lower bounds for dynamic connectivity. Mihai Patrascu, Erik D. Demaine |
| 2004 | Lower bounds for linear degeneracy testing. Nir Ailon, Bernard Chazelle |
| 2004 | Lower bounds for local search by quantum arguments. Scott Aaronson |
| 2004 | Multi-linear formulas for permanent and determinant are of super-polynomial size. Ran Raz |
| 2004 | Multi-processor scheduling to minimize flow time with epsilon resource augmentation. Chandra Chekuri, Ashish Goel, Sanjeev Khanna, Amit Kumar |
| 2004 | Multilinear formulas and skepticism of quantum computing. Scott Aaronson |
| 2004 | Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. Daniel A. Spielman, Shang-Hua Teng |
| 2004 | Network games. Éva Tardos |
| 2004 | New hardness results for congestion minimization and machine scheduling. Julia Chuzhoy, Joseph Naor |
| 2004 | New notions of security: achieving universal composability without trusted setup. Manoj Prabhakaran, Amit Sahai |
| 2004 | On coresets for k-means and k-median clustering. Sariel Har-Peled, Soham Mazumdar |
| 2004 | On sums of independent random variables with unbounded variance, and estimating the average degree in a graph. Uriel Feige |
| 2004 | On the performance of greedy algorithms in packet buffering. Susanne Albers, Markus Schmidt |
| 2004 | Primal-dual algorithms for deterministic inventory problems. Retsef Levi, Robin Roundy, David B. Shmoys |
| 2004 | Proceedings of the 36th Annual ACM Symposium on Theory of Computing, Chicago, IL, USA, June 13-16, 2004 László Babai |
| 2004 | Quantum algorithms a decade after shor. Andris Ambainis |
| 2004 | Quantum and classical query complexities of local search are polynomially related. Miklos Santha, Mario Szegedy |
| 2004 | Rational secret sharing and multiparty computation: extended abstract. Joseph Y. Halpern, Vanessa Teague |
| 2004 | Robust pcps of proximity, shorter pcps and applications to coding. Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan |
| 2004 | Sharp thresholds For monotone properties in random geometric graphs. Ashish Goel, Sanatan Rai, Bhaskar Krishnamachari |
| 2004 | Solving fractional packing problems in Daniel Bienstock, Garud Iyengar |
| 2004 | Sorting and searching in the presence of memory faults (without redundancy). Irene Finocchi, Giuseppe F. Italiano |
| 2004 | Spectral partitioning, eigenvalue bounds, and circle packings for graphs of bounded genus. Jonathan A. Kelner |
| 2004 | Sublinear algorithms for testing monotone and unimodal distributions. Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld |
| 2004 | The all-or-nothing multicommodity flow problem. Chandra Chekuri, Sanjeev Khanna, F. Bruce Shepherd |
| 2004 | The complexity of pure Nash equilibria. Alex Fabrikant, Christos H. Papadimitriou, Kunal Talwar |
| 2004 | The difficulty of testing for isomorphism against a graph that is given in advance. Eldar Fischer |
| 2004 | The quantum adiabatic optimization algorithm and local minima. Ben Reichardt |
| 2004 | The spending constraint model for market equilibrium: algorithmic, existence and uniqueness results. Nikhil R. Devanur |
| 2004 | The two possible values of the chromatic number of a random graph. Dimitris Achlioptas, Assaf Naor |
| 2004 | The zero-one principle for switching networks. Yossi Azar, Yossi Richter |
| 2004 | Typical properties of winners and losers in discrete optimization. René Beier, Berthold Vöcking |
| 2004 | Unconditional lower bounds on the time-approximation tradeoffs for the distributed minimum spanning tree problem. Michael Elkin |
| 2004 | Using mixture models for collaborative filtering. Jon M. Kleinberg, Mark Sandler |
| 2004 | Using nondeterminism to amplify hardness. Alexander Healy, Salil P. Vadhan, Emanuele Viola |
| 2004 | Visibly pushdown languages. Rajeev Alur, P. Madhusudan |