| 2010 | Approximation Algorithms for the Edge-Disjoint Paths Problem via Raecke Decompositions. | Matthew Andrews |
| 2010 | Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2010 | Solving Linear Systems through Nested Dissection. | Noga Alon, Raphael Yuster |
| 2010 | A Non-linear Lower Bound for Planar Epsilon-Nets. | Noga Alon |
| 2009 | Symmetry and Approximability of Submodular Maximization Problems. | Jan Vondrk |
| 2009 | A Probabilistic Inequality with Applications to Threshold Direct-Product Theorems. | Falk Unger |
| 2009 | Distance Oracles for Sparse Graphs. | Christian Sommer, Elad Verbin, Wei Yu |
| 2009 | The Intersection of Two Halfspaces Has High Threshold Degree. | Alexander A. Sherstov |
| 2009 | Breaking the Multicommodity Flow Barrier for O(vlog n)-Approximations to Sparsest Cut. | Jonah Sherman |
| 2009 | Smoothed Analysis of Multiobjective Optimization. | Heiko Rglin, Shang-Hua Teng |
| 2009 | Span Programs and Quantum Query Complexity: The General Adversary Bound Is Nearly Tight for Every Boolean Function. | Ben Reichardt |
| 2009 | How to Round Any CSP. | Prasad Raghavendra, David Steurer |
| 2009 | Integrality Gaps for Strong SDP Relaxations of UNIQUE GAMES. | Prasad Raghavendra, David Steurer |
| 2009 | Exact and Approximate Pattern Matching in the Streaming Model. | Benny Porat, Ely Porat |
| 2009 | KKL, Kruskal-Katona, and Monotone Nets. | Ryan O'Donnell, Karl Wimmer |
| 2009 | Approximating Minimum Cost Connectivity Problems via Uncrossable Bifamilies and Spider-Cover Decompositions. | Zeev Nutov |
| 2009 | Bit Encryption Is Complete. | Steven A. Myers, Abhi Shelat |
| 2009 | Convergence to Equilibrium in Local Interaction Games. | Andrea Montanari, Amin Saberi |
| 2009 | Approximation Algorithms for Multicommodity-Type Problems with Guarantees Independent of the Graph Size. | Ankur Moitra |
| 2009 | Combinatorial PCPs with Efficient Verifiers. | Or Meir |
| 2009 | The Communication Complexity of Set-Disjointness with Small Sets and 0-1 Intersection. | Eyal Kushilevitz, Enav Weinreb |
| 2009 | Reducibility among Fractional Stability Problems. | Shiva Kintali, Laura J. Poplawski, Rajmohan Rajaraman, Ravi Sundaram, Shang-Hua Teng |
| 2009 | SDP Integrality Gaps with Local ell_1-Embeddability. | Subhash Khot, Rishi Saket |
| 2009 | Faster Generation of Random Spanning Trees. | Jonathan A. Kelner, Aleksander Madry |
| 2009 | Higher Eigenvalues of Graphs. | Jonathan A. Kelner, James R. Lee, Gregory N. Price, Shang-Hua Teng |