| 2005 | Extractors with weak random seeds. | Ran Raz |
| 2005 | New and improved constructions of non-malleable cryptographic protocols. | Rafael Pass, Alon Rosen |
| 2005 | Computing correlated equilibria in multi-player games. | Christos H. Papadimitriou |
| 2005 | Low distortion embeddings for edit distance. | Rafail Ostrovsky, Yuval Rabani |
| 2005 | Balanced metric labeling. | Joseph Naor, Roy Schwartz |
| 2005 | Learning nonsingular phylogenies and hidden Markov models. | Elchanan Mossel, Sbastien Roch |
| 2005 | On dynamic range reporting in one dimension. | Christian Worm Mortensen, Rasmus Pagh, Mihai Patrascu |
| 2005 | The mixing time of the Thorp shuffle. | Ben Morris |
| 2005 | Collusion-free protocols. | Matt Lepinski, Silvio Micali, Abhi Shelat |
| 2005 | Bounded-depth circuits: separating wires from gates. | Michal Kouck, Pavel Pudlk, Denis Thrien |
| 2005 | Learning with attribute costs. | Haim Kaplan, Eyal Kushilevitz, Yishay Mansour |
| 2005 | Concurrent general composition of secure protocols in the timing model. | Yael Tauman Kalai, Yehuda Lindell, Manoj Prabhakaran |
| 2005 | Universal approximations for TSP, Steiner tree, and set cover. | Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, Ravi Sundaram |
| 2005 | An optimal multi-writer snapshot algorithm. | Prasad Jayanti |
| 2005 | On strip packing With rotations. | Klaus Jansen, Rob van Stee |
| 2005 | Optimal approximations of the frequency moments of data streams. | Piotr Indyk, David P. Woodruff |
| 2005 | Key agreement from weak bit agreement. | Thomas Holenstein |
| 2005 | Every 2-CSP allows nontrivial approximation. | Johan Hstad |
| 2005 | Fast quantum algorithms for computing the unit group and class group of a number field. | Sean Hallgren |
| 2005 | Oblivious routing in directed graphs with random demands. | Mohammad Taghi Hajiaghayi, Jeong Han Kim, Tom Leighton, Harald Rcke |
| 2005 | Limits to list decoding Reed-Solomon codes. | Venkatesan Guruswami, Atri Rudra |
| 2005 | Edge partition of planar sraphs into two outerplanar graphs. | Daniel Gonalves |
| 2005 | Saving an epsilon: a 2-approximation for the k-MST problem in graphs. | Naveen Garg |
| 2005 | From a static impossibility to an adaptive lower bound: the complexity of early deciding set agreement. | Eli Gafni, Rachid Guerraoui, Bastian Pochon |
| 2005 | Efficient testing of groups. | Katalin Friedl, Gbor Ivanyos, Miklos Santha |