| 2005 | A Recursive Greedy Algorithm for Walks in Directed Graphs. | Chandra Chekuri, Martin Pl |
| 2005 | Algorithmic Techniques and Tools from Computational Geometry. | Bernard Chazelle |
| 2005 | Error Correction via Linear Programming. | Emmanuel J. Cands, Mark Rudelson, Terence Tao, Roman Vershynin |
| 2005 | Analysis and Prediction of the Long-Run Behavior of Probabilistic Sequential Programs with Recursion (Extended Abstract). | Toms Brzdil, Javier Esparza, Antonn Kucera |
| 2005 | On the Complexity of Real Functions. | Mark Braverman |
| 2005 | Nash Equilibria in Random Games. | Imre Brny, Santosh S. Vempala, Adrian Vetta |
| 2005 | How To Play Almost Any Mental Game Over The Net - Concurrent Composition via Super-Polynomial Simulation. | Boaz Barak, Amit Sahai |
| 2005 | A Tale of Two Dimensional Bin Packing. | Nikhil Bansal, Andrea Lodi, Maxim Sviridenko |
| 2005 | Mechanism Design via Machine Learning. | Maria-Florina Balcan, Avrim Blum, Jason D. Hartline, Yishay Mansour |
| 2005 | From optimal measurement to efficient quantum algorithms for the hidden subgroup problem over semidirect product groups. | Dave Bacon, Andrew M. Childs, Wim van Dam |
| 2005 | Fast Algorithms for Approximate Semide.nite Programming using the Multiplicative Weights Update Method. | Sanjeev Arora, Elad Hazan, Satyen Kale |
| 2005 | On Non-Approximability for Quadratic Programs. | Sanjeev Arora, Eli Berger, Elad Hazan, Guy Kindler, Muli Safra |
| 2005 | Hardness of the Undirected Edge-Disjoint Paths Problem with Congestion. | Matthew Andrews, Julia Chuzhoy, Sanjeev Khanna, Lisa Zhang |
| 2005 | Additive Approximation for Edge-Deletion Problems. | Noga Alon, Asaf Shapira, Benny Sudakov |
| 2005 | A Characterization of the (natural) Graph Properties Testable with One-Sided Error. | Noga Alon, Asaf Shapira |
| 2005 | Hardness of Approximating the Closest Vector Problem with Pre-Processing. | Mikhail Alekhnovich, Subhash Khot, Guy Kindler, Nisheeth K. Vishnoi |
| 2005 | Fitting tree metrics: Hierarchical clustering and Phylogeny. | Nir Ailon, Moses Charikar |
| 2005 | Metric Embeddings with Relaxed Guarantees. | Ittai Abraham, Yair Bartal, T.-H. Hubert Chan, Kedar Dhamdhere, Anupam Gupta, Jon M. Kleinberg, Ofer Neiman, Aleksandrs Slivkins |
| 2005 | On the Complexity of Two-PlayerWin-Lose Games. | Timothy G. Abbott, Daniel Kane, Paul Valiant |
| 2004 | Holographic Algorithms (Extended Abstract). | Leslie G. Valiant |
| 2004 | An Unconditional Study of Computational Zero Knowledge. | Salil P. Vadhan |
| 2004 | Quantum Speed-Up of Markov Chain Based Algorithms. | Mario Szegedy |
| 2004 | Stochastic Optimization is (Almost) as easy as Deterministic Optimization. | David B. Shmoys, Chaitanya Swamy |
| 2004 | Exponentially Many Steps for Finding a Nash Equilibrium in a Bimatrix Game. | Rahul Savani, Bernhard von Stengel |
| 2004 | Dynamic Transitive Closure via Dynamic Matrix Inverse (Extended Abstract). | Piotr Sankowski |