| 2008 | On Basing Lower-Bounds for Learning on Worst-Case Assumptions. | Benny Applebaum, Boaz Barak, David Xiao |
| 2008 | Hardness of Nearest Neighbor under L-infinity. | Alexandr Andoni, Dorian Croitoru, Mihai Patrascu |
| 2008 | k-Wise Independent Random Graphs. | Noga Alon, Asaf Nussboim |
| 2008 | Broadcasting with Side Information. | Noga Alon, Eyal Lubetzky, Uri Stav, Amit Weinstein, Avinatan Hassidim |
| 2008 | Arithmetic Circuits: A Chasm at Depth Four. | Manindra Agrawal, V. Vinay |
| 2008 | Theory of Sponsored Search Auctions. | Gagan Aggarwal, S. Muthukrishnan |
| 2008 | Algorithmic Barriers from Phase Transitions. | Dimitris Achlioptas, Amin Coja-Oghlan |
| 2008 | Nearly Tight Low Stretch Spanning Trees. | Ittai Abraham, Yair Bartal, Ofer Neiman |
| 2008 | The Polynomial Method in Quantum and Classical Computing. | Scott Aaronson |
| 2007 | One-Way Multi-Party Communication Lower Bound for Pointer Jumping with Applications. | Emanuele Viola, Avi Wigderson |
| 2007 | Structure and Randomness in Combinatorics. | Terence Tao |
| 2007 | Adaptive Simulated Annealing: A Near-optimal Connection between Sampling and Counting. | Daniel Stefankovic, Santosh S. Vempala, Eric Vigoda |
| 2007 | Spectral Graph Theory and its Applications. | Daniel A. Spielman |
| 2007 | Simulating Quantum Correlations with Finite Communication. | Oded Regev, Ben Toner |
| 2007 | A Lower Bound for the Size of Syntactically Multilinear Arithmetic Circuits. | Ran Raz, Amir Shpilka, Amir Yehudayoff |
| 2007 | Strong Lower Bounds for Approximating Distribution Support Size and the Distinct Elements Problem. | Sofya Raskhodnikova, Dana Ron, Amir Shpilka, Adam D. Smith |
| 2007 | Planning for Fast Connectivity Updates. | Mihai Patrascu, Mikkel Thorup |
| 2007 | Mechanism Design via Differential Privacy. | Frank McSherry, Kunal Talwar |
| 2007 | On the Optimality of Planar and Geometric Approximation Schemes. | Dniel Marx |
| 2007 | Can you beat treewidth? | Dniel Marx |
| 2007 | Non-Linear Index Coding Outperforming the Linear Optimum. | Eyal Lubetzky, Uri Stav |
| 2007 | Mixing Time Power Laws at Criticality. | Yun Long, Asaf Nachmias, Yuval Peres |
| 2007 | Beating Simplex for Fractional Packing and Covering Linear Programs. | Christos Koufogiannakis, Neal E. Young |
| 2007 | Near Optimal Bounds for Collision in Pollard Rho for Discrete Log. | Jeong Han Kim, Ravi Montenegro, Prasad Tetali |
| 2007 | Linear Equations Modulo 2 and the L1 Diameter of Convex Bodies. | Subhash Khot, Assaf Naor |