| 2005 | Computing the first Betti number and the connected components of semi-algebraic sets. | Saugata Basu, Richard Pollack, Marie-Franoise Roy |
| 2005 | Polynomial time algorithm for computing the top Betti numbers of semi-algebraic sets defined by quadratic inequalities. | Saugata Basu |
| 2005 | Simulating independence: new constructions of condensers, ramsey graphs, dispersers, and extractors. | Boaz Barak, Guy Kindler, Ronen Shaltiel, Benny Sudakov, Avi Wigderson |
| 2005 | Low-distortion embeddings of general metrics into the line. | Mihai Badoiu, Julia Chuzhoy, Piotr Indyk, Anastasios Sidiropoulos |
| 2005 | Convex programming for scheduling unrelated parallel machines. | Yossi Azar, Amir Epstein |
| 2005 | The Price of Routing Unsplittable Flow. | Baruch Awerbuch, Yossi Azar, Amir Epstein |
| 2005 | Euclidean distortion and the sparsest cut. | Sanjeev Arora, James R. Lee, Assaf Naor |
| 2005 | Hardness of the undirected congestion minimization problem. | Matthew Andrews, Lisa Zhang |
| 2005 | Hardness of the undirected edge-disjoint paths problem. | Matthew Andrews, Lisa Zhang |
| 2005 | Every monotone graph property is testable. | Noga Alon, Asaf Shapira |
| 2005 | Quadratic forms on graphs. | Noga Alon, Konstantin Makarychev, Yury Makarychev, Assaf Naor |
| 2005 | Towards strong nonapproximability results in the Lovasz-Schrijver hierarchy. | Michael Alekhnovich, Sanjeev Arora, Iannis Tourlakis |
| 2005 | Lower bounds for k-DNF resolution on random 3-CNFs. | Michael Alekhnovich |
| 2005 | Representing hard lattices with O(n log n) bits. | Mikls Ajtai |
| 2005 | Aggregating inconsistent information: ranking and clustering. | Nir Ailon, Moses Charikar, Alantha Newman |
| 2005 | Covert two-party computation. | Luis von Ahn, Nicholas J. Hopper, John Langford |
| 2005 | Derandomization of auctions. | Gagan Aggarwal, Amos Fiat, Andrew V. Goldberg, Jason D. Hartline, Nicole Immorlica, Madhu Sudan |
| 2005 | O(sqrt(log n)) approximation algorithms for min UnCut, min 2CNF deletion, and directed cut problems. | Amit Agarwal, Moses Charikar, Konstantin Makarychev, Yury Makarychev |
| 2005 | Towards asymptotic optimality in probabilistic packet marking. | Micah Adler, Jeff Edmonds, Jir Matousek |
| 2005 | On the bias of traceroute sampling: or, power-law degree distributions in regular graphs. | Dimitris Achlioptas, Aaron Clauset, David Kempe, Cristopher Moore |
| 2005 | The complexity of agreement. | Scott Aaronson |
| 2004 | Graph entropy and quantum sorting problems. | Andrew Chi-Chih Yao |
| 2004 | Depth through breadth, or why should we attend talks in other areas? | Avi Wigderson |
| 2004 | Network games. | va Tardos |
| 2004 | Bypassing the embedding: algorithms for low dimensional metrics. | Kunal Talwar |