| 2007 | An approximation algorithm for max-min fair allocation of indivisible goods. | Arash Asadpour, Amin Saberi |
| 2007 | A combinatorial, primal-dual approach to semidefinite programs. | Sanjeev Arora, Satyen Kale |
| 2007 | Terminal backup, 3D matching, and covering cubic graphs. | Elliot Anshelevich, Adriana Karagiozova |
| 2007 | Stability of the max-weight routing and scheduling protocol in dynamic networks and at critical loads. | Matthew Andrews, Kyomin Jung, Alexander L. Stolyar |
| 2007 | Testing k-wise and almost k-wise independence. | Noga Alon, Alexandr Andoni, Tali Kaufman, Kevin Matulef, Ronitt Rubinfeld, Ning Xie |
| 2007 | Improved approximation for directed cut problems. | Amit Agarwal, Noga Alon, Moses Charikar |
| 2007 | Local embeddings of metric spaces. | Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2006 | Linear degree extractors and the inapproximability of max clique and chromatic number. | David Zuckerman |
| 2006 | New upper and lower bounds for randomized and quantum local search. | Shengyu Zhang |
| 2006 | Counting independent sets up to the tree threshold. | Dror Weitz |
| 2006 | Zero-knowledge against quantum attacks. | John Watrous |
| 2006 | Finding a maximum weight triangle in n | Virginia Vassilevska, Ryan Williams |
| 2006 | The DLT priority sampling is essentially optimal. | Mario Szegedy |
| 2006 | A combinatorial characterization of the testable graph properties: it's all about regularity. | Noga Alon, Eldar Fischer, Ilan Newman, Asaf Shapira |
| 2006 | Gowers uniformity, influence of variables, and PCPs. | Alex Samorodnitsky, Luca Trevisan |
| 2006 | New trade-offs in cost-sharing mechanisms. | Tim Roughgarden, Mukund Sundararajan |
| 2006 | A quasi-polynomial time approximation scheme for minimum weight triangulation. | Jan Remy, Angelika Steger |
| 2006 | Pseudorandom walks on regular digraphs and the RL vs. L problem. | Omer Reingold, Luca Trevisan, Salil P. Vadhan |
| 2006 | Lattice problems and norm embeddings. | Oded Regev, Ricky Rosen |
| 2006 | Extractors for a constant number of polynomially small min-entropy independent sources. | Anup Rao |
| 2006 | The changing face of web search: algorithms, auctions and advertising. | Prabhakar Raghavan |
| 2006 | An efficient algorithm for solving word equations. | Wojciech Plandowski |
| 2006 | Time-space trade-offs for predecessor search. | Mihai Patrascu, Mikkel Thorup |
| 2006 | On adequate performance measures for paging. | Konstantinos Panagiotou, Alexander Souza |
| 2006 | Narrow proofs may be spacious: separating space and width in resolution. | Jakob Nordstrm |