| 2003 | Better streaming algorithms for clustering problems. | Moses Charikar, Liadan O'Callaghan, Rina Panigrahy |
| 2003 | OPT versus LOAD in dynamic storage allocation. | Adam L. Buchsbaum, Howard J. Karloff, Claire Kenyon, Nick Reingold, Mikkel Thorup |
| 2003 | On the limits of cache-obliviousness. | Gerth Stlting Brodal, Rolf Fagerberg |
| 2003 | Modified log-sobolev inequalities, mixing and hypercontractivity. | Sergey G. Bobkov, Prasad Tetali |
| 2003 | Randomness-efficient low degree tests and short PCPs via epsilon-biased sets. | Eli Ben-Sasson, Madhu Sudan, Salil P. Vadhan, Avi Wigderson |
| 2003 | Some 3CNF properties are hard to test. | Eli Ben-Sasson, Prahladh Harsha, Sofya Raskhodnikova |
| 2003 | Random knapsack in expected polynomial time. | Ren Beier, Berthold Vcking |
| 2003 | A sublinear algorithm for weakly approximating edit distance. | Tugkan Batu, Funda Ergn, Joe Kilian, Avner Magen, Sofya Raskhodnikova, Ronitt Rubinfeld, Rahul Sami |
| 2003 | On metric ramsey-type phenomena. | Yair Bartal, Nathan Linial, Manor Mendel, Assaf Naor |
| 2003 | Sampling lower bounds via information theory. | Ziv Bar-Yossef |
| 2003 | Server scheduling in the L | Nikhil Bansal, Kirk Pruhs |
| 2003 | Management of multi-queue switches in QoS networks. | Yossi Azar, Yossi Richter |
| 2003 | Optimal oblivious routing in polynomial time. | Yossi Azar, Edith Cohen, Amos Fiat, Haim Kaplan, Harald Rcke |
| 2003 | Reducing truth-telling online mechanisms to online optimization. | Baruch Awerbuch, Yossi Azar, Adam Meyerson |
| 2003 | Distinct distances in three and higher dimensions. | Boris Aronov, Jnos Pach, Micha Sharir, Gbor Tardos |
| 2003 | Cutting triangular cycles of lines in space. | Boris Aronov, Vladlen Koltun, Micha Sharir |
| 2003 | Near-optimal network design with selfish agents. | Elliot Anshelevich, Anirban Dasgupta, va Tardos, Tom Wexler |
| 2003 | Constant factor approximation of vertex-cuts in planar graphs. | Eyal Amir, Robert Krauthgamer, Satish Rao |
| 2003 | Testing subgraphs in directed graphs. | Noga Alon, Asaf Shapira |
| 2003 | The online set cover problem. | Noga Alon, Baruch Awerbuch, Yossi Azar, Niv Buchbinder, Joseph Naor |
| 2003 | The worst-case behavior of schnorr's algorithm approximating the shortest nonzero vector in a lattice. | Mikls Ajtai |
| 2003 | Adiabatic quantum state generation and statistical zero knowledge. | Dorit Aharonov, Amnon Ta-Shma |
| 2003 | A stochastic process on the hypercube with applications to peer-to-peer networks. | Micah Adler, Eran Halperin, Richard M. Karp, Vijay V. Vazirani |
| 2003 | The threshold for random k-SAT is 2 | Dimitris Achlioptas, Yuval Peres |
| 2002 | Pseudo-random generators for all hardnesses. | Christopher Umans |