| 2012 | An Additive Combinatorics Approach Relating Rank to Communication Complexity. | Eli Ben-Sasson, Shachar Lovett, Noga Ron-Zewi |
| 2012 | Learning-Graph-Based Quantum Algorithm for k-Distinctness. | Aleksandrs Belovs |
| 2012 | Large Deviation Bounds for Decision Trees and Sampling Lower Bounds for AC0-Circuits. | Chris Beck, Russell Impagliazzo, Shachar Lovett |
| 2012 | The Locality of Distributed Symmetry Breaking. | Leonid Barenboim, Michael Elkin, Seth Pettie, Johannes Schneider |
| 2012 | Making the Long Code Shorter. | Boaz Barak, Parikshit Gopalan, Johan Hstad, Raghu Meka, Prasad Raghavendra, David Steurer |
| 2012 | Active Property Testing. | Maria-Florina Balcan, Eric Blais, Avrim Blum, Liu Yang |
| 2012 | Learning Topic Models - Going beyond SVD. | Sanjeev Arora, Rong Ge, Ankur Moitra |
| 2012 | How to Allocate Tasks Asynchronously. | Dan Alistarh, Michael A. Bender, Seth Gilbert, Rachid Guerraoui |
| 2012 | On Range Searching with Semialgebraic Sets II. | Pankaj K. Agarwal, Jir Matousek, Micha Sharir |
| 2011 | Separator Theorems for Minor-Free and Shallow Minor-Free Graphs with Applications. | Christian Wulff-Nilsen |
| 2011 | Randomness Buys Depth for Approximate Counting. | Emanuele Viola |
| 2011 | Extractors for Circuit Sources. | Emanuele Viola |
| 2011 | The Power of Linear Estimators. | Gregory Valiant, Paul Valiant |
| 2011 | Computing Blindfolded: New Developments in Fully Homomorphic Encryption. | Vinod Vaikuntanathan |
| 2011 | Quadratic Goldreich-Levin Theorems. | Madhur Tulsiani, Julia Wolf |
| 2011 | Dispersers for Affine Sources with Sub-polynomial Entropy. | Ronen Shaltiel |
| 2011 | Medium Access Using Queues. | Devavrat Shah, Jinwoo Shin, Prasad Tetali |
| 2011 | Maximum Edge-Disjoint Paths in Planar Graphs with Congestion 2. | Loc Seguin-Charbonneau, F. Bruce Shepherd |
| 2011 | Minimum Weight Cycles and Triangles: Equivalences and Algorithms. | Liam Roditty, Virginia Vassilevska Williams |
| 2011 | Improved Mixing Condition on the Grid for Counting and Sampling Independent Sets. | Ricardo Restrepo, Jinwoo Shin, Prasad Tetali, Eric Vigoda, Linji Yang |
| 2011 | Green Computing Algorithmics. | Kirk Pruhs |
| 2011 | (1 + eps)-Approximate Sparse Recovery. | Eric Price, David P. Woodruff |
| 2011 | Online Node-Weighted Steiner Tree and Related Problems. | Joseph Naor, Debmalya Panigrahi, Mohit Singh |
| 2011 | Approximating Graphic TSP by Matchings. | Tobias Mmke, Ola Svensson |
| 2011 | Maximizing Expected Utility for Stochastic Combinatorial Optimization Problems. | Jian Li, Amol Deshpande |