| 2004 | Cryptography in NC | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
| 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 | Hardness of Buy-at-Bulk Network Design. | Matthew Andrews |
| 2004 | Quantum Walk Algorithm for Element Distinctness. | Andris Ambainis |
| 2004 | Learnability and Automatizability. | Michael Alekhnovich, Mark Braverman, Vitaly Feldman, Adam R. Klivans, Toniann Pitassi |
| 2004 | Lattice Problems in NP cap coNP. | Dorit Aharonov, Oded Regev |
| 2004 | Adiabatic Quantum Computation is Equivalent to Standard Quantum Computation. | Dorit Aharonov, Wim van Dam, Julia Kempe, Zeph Landau, Seth Lloyd, Oded Regev |
| 2004 | On the Streaming Model Augmented with a Sorting Primitive. | Gagan Aggarwal, Mayur Datar, Sridhar Rajagopalan, Matthias Ruhl |
| 2003 | Performance Analysis of Dynamic Network Processes. | Eli Upfal |
| 2003 | List-Decoding Using The XOR Lemma. | Luca Trevisan |
| 2003 | Solving Sparse, Symmetric, Diagonally-Dominant Linear Systems in Time 0(m | Daniel A. Spielman, Shang-Hua Teng |
| 2003 | Mixing. | Dana Randall |
| 2003 | Bounded-Concurrent Secure Two-Party Computation in a Constant Number of Rounds. | Rafael Pass, Alon Rosen |
| 2003 | Group Strategyproof Mechanisms via Primal-Dual Algorithms. | Martin Pl, va Tardos |
| 2003 | Always Good Turing: Asymptotically Optimal Probability Estimation. | Alon Orlitsky, Narayana P. Santhanam, Junan Zhang |
| 2003 | Proofs of the Parisi and Coppersmith-Sorkin Conjectures for the Finite Random Assignment Problem. | Chandra Nair, Balaji Prabhakar, Mayank Sharma |
| 2003 | On e-Biased Generators in NC0. | Elchanan Mossel, Amir Shpilka, Luca Trevisan |
| 2003 | The Resolution Complexity of Random Constraint Satisfaction Problems. | Michael Molloy, Mohammad R. Salavatipour |
| 2003 | On Certain Connectivity Properties of the Internet Topology. | Milena Mihail, Christos H. Papadimitriou, Amin Saberi |
| 2003 | Zero-Knowledge Sets. | Silvio Micali, Michael O. Rabin, Joe Kilian |
| 2003 | The Ising Model on Trees: Boundary Conditions and Mixing Time. | Fabio Martinelli, Alistair Sinclair, Dror Weitz |
| 2003 | Logconcave Functions: Geometry and Efficient Sampling Algorithms | Lszl Lovsz, Santosh S. Vempala |
| 2003 | Simulated Annealing in Convex Bodies and an 0*(n4) Volume Algorithm. | Lszl Lovsz, Santosh S. Vempala |
| 2003 | General Composition and Universal Composability in Secure Multi-Party Computation. | Yehuda Lindell |
| 2003 | Towards a Characterization of Truthful Combinatorial Auctions. | Ron Lavi, Ahuva Mu'alem, Noam Nisan |