| 2004 | Isotopic implicit surface meshing. | Jean-Daniel Boissonnat, David Cohen-Steiner, Gert Vegter |
| 2004 | Solving fractional packing problems in | Daniel Bienstock, Garud Iyengar |
| 2004 | Robust pcps of proximity, shorter pcps and applications to coding. | Eli Ben-Sasson, Oded Goldreich, Prahladh Harsha, Madhu Sudan, Salil P. Vadhan |
| 2004 | Typical properties of winners and losers in discrete optimization. | Ren Beier, Berthold Vcking |
| 2004 | Sublinear algorithms for testing monotone and unimodal distributions. | Tugkan Batu, Ravi Kumar, Ronitt Rubinfeld |
| 2004 | Exponential separation of quantum and classical one-way communication complexity. | Ziv Bar-Yossef, T. S. Jayram, Iordanis Kerenidis |
| 2004 | Approximation algorithms for deadline-TSP and vehicle routing with time-windows. | Nikhil Bansal, Avrim Blum, Shuchi Chawla, Adam Meyerson |
| 2004 | The zero-one principle for switching networks. | Yossi Azar, Yossi Richter |
| 2004 | Adaptive routing with end-to-end feedback: distributed learning and geometric approaches. | Baruch Awerbuch, Robert D. Kleinberg |
| 2004 | Expander flows, geometric embeddings and graph partitioning. | Sanjeev Arora, Satish Rao, Umesh V. Vazirani |
| 2004 | Quantum algorithms a decade after shor. | Andris Ambainis |
| 2004 | Visibly pushdown languages. | Rajeev Alur, P. Madhusudan |
| 2004 | Approximating the cut-norm via Grothendieck's inequality. | Noga Alon, Assaf Naor |
| 2004 | On the performance of greedy algorithms in packet buffering. | Susanne Albers, Markus Schmidt |
| 2004 | A conjecture about polynomial time computable lattice-lattice functions. | Mikls Ajtai |
| 2004 | Lower bounds for linear degeneracy testing. | Nir Ailon, Bernard Chazelle |
| 2004 | The two possible values of the chromatic number of a random graph. | Dimitris Achlioptas, Assaf Naor |
| 2004 | Lower bounds for local search by quantum arguments. | Scott Aaronson |
| 2004 | Multilinear formulas and skepticism of quantum computing. | Scott Aaronson |
| 2003 | On the power of quantum fingerprinting. | Andrew Chi-Chih Yao |
| 2003 | Approximation schemes for clustering problems. | Wenceslas Fernandez de la Vega, Marek Karpinski, Claire Kenyon, Yuval Rabani |
| 2003 | Space efficient dynamic stabbing with fast queries. | Mikkel Thorup |
| 2003 | Integer priority queues with decrease key in constant time and the single source shortest paths problem. | Mikkel Thorup |
| 2003 | Optimal probabilistic fingerprint codes. | Gbor Tardos |
| 2003 | Time-space tradeoff lower bounds for integer multiplication and graphs of arithmetic functions. | Martin Sauerhoff, Philipp Woelfel |