| 2009 | Instance-Optimal Geometric Algorithms. | Peyman Afshani, Jrmy Barbay, Timothy M. Chan |
| 2009 | Orthogonal Range Reporting in Three and Higher Dimensions. | Peyman Afshani, Lars Arge, Kasper Dalgaard Larsen |
| 2008 | Matrix Sparsification for Rank and Determinant Computations via Nested Dissection. | Raphael Yuster |
| 2008 | Average-case Complexity. | Luca Trevisan |
| 2008 | Submodular Approximation: Sampling-based Algorithms and Lower Bounds. | Zoya Svitkina, Lisa Fleischer |
| 2008 | The Unbounded-Error Communication Complexity of Symmetric Functions. | Alexander A. Sherstov |
| 2008 | Linear Level Lasserre Lower Bounds for Certain k-CSPs. | Grant Schoenebeck |
| 2008 | Sequence Length Requirement of Distance-Based Phylogeny Reconstruction: Breaking the Polynomial Barrier. | Sbastien Roch |
| 2008 | Dense Subsets of Pseudorandom Sets. | Omer Reingold, Luca Trevisan, Madhur Tulsiani, Salil P. Vadhan |
| 2008 | Multilinear Formulas, Maximal-Partition Discrepancy and Mixed-Sources Extractors. | Ran Raz, Amir Yehudayoff |
| 2008 | The Sign-Rank of AC^O. | Alexander A. Razborov, Alexander A. Sherstov |
| 2008 | A Counterexample to Strong Parallel Repetition. | Ran Raz |
| 2008 | (Data) STRUCTURES. | Mihai Patrascu |
| 2008 | Succincter. | Mihai Patrascu |
| 2008 | On the Hardness of Being Truthful. | Christos H. Papadimitriou, Michael Schapira, Yaron Singer |
| 2008 | A Geometric Approach to Lower Bounds for Approximate Near-Neighbor Search and Partial Match. | Rina Panigrahy, Kunal Talwar, Udi Wieder |
| 2008 | Constant-Time Approximation Algorithms via Local Improvements. | Huy N. Nguyen, Krzysztof Onak |
| 2008 | Gaussian Bounds for Noise Correlation of Functions and Tight Analysis of Long Codes. | Elchanan Mossel |
| 2008 | Two Query PCP with Sub-Constant Error. | Dana Moshkovitz, Ran Raz |
| 2008 | Some Results on Greedy Embeddings in Metric Spaces. | Ankur Moitra, Tom Leighton |
| 2008 | Inapproximability for Metric Embeddings into R^d. | Jir Matousek, Anastasios Sidiropoulos |
| 2008 | (Acyclic) JobShops are Hard to Approximate. | Monaldo Mastrolilli, Ola Svensson |
| 2008 | Clock Synchronization with Bounded Global and Local Skew. | Christoph Lenzen, Thomas Locher, Roger Wattenhofer |
| 2008 | Learning Geometric Concepts via Gaussian Surface Area. | Adam R. Klivans, Ryan O'Donnell, Rocco A. Servedio |
| 2008 | Spherical Cubes and Rounding in High Dimensions. | Guy Kindler, Ryan O'Donnell, Anup Rao, Avi Wigderson |