| 2011 | Efficient Fully Homomorphic Encryption from (Standard) LWE. | Zvika Brakerski, Vinod Vaikuntanathan |
| 2011 | Near Optimal Column-Based Matrix Reconstruction. | Christos Boutsidis, Petros Drineas, Malik Magdon-Ismail |
| 2011 | Multiple-Source Multiple-Sink Maximum Flow in Directed Planar Graphs in Near-Linear Time. | Glencora Borradaile, Philip N. Klein, Shay Mozes, Yahav Nussbaum, Christian Wulff-Nilsen |
| 2011 | A Constant Factor Approximation Algorithm for Unsplittable Flow on Paths. | Paul S. Bonsma, Jens Schulz, Andreas Wiese |
| 2011 | Pseudorandomness for Read-Once Formulas. | Andrej Bogdanov, Periklis A. Papakonstantinou, Andrew Wan |
| 2011 | Welfare and Profit Maximization with Production Costs. | Avrim Blum, Anupam Gupta, Yishay Mansour, Ankit Sharma |
| 2011 | Which Networks are Least Susceptible to Cascading Failures? | Lawrence E. Blume, David A. Easley, Jon M. Kleinberg, Robert Kleinberg, va Tardos |
| 2011 | Lexicographic Products and the Power of Non-linear Network Coding. | Anna Blasiak, Robert Kleinberg, Eyal Lubetzky |
| 2011 | How Bad is Forming Your Own Opinion? | David Bindel, Jon M. Kleinberg, Sigal Oren |
| 2011 | Tight Lower Bounds for 2-query LCCs over Finite Fields. | Arnab Bhattacharyya, Zeev Dvir, Amir Shpilka, Shubhangi Saraf |
| 2011 | Mutual Exclusion with O(log^2 Log n) Amortized Work. | Michael A. Bender, Seth Gilbert |
| 2011 | Fully Dynamic Maximal Matching in O (log n) Update Time. | Surender Baswana, Manoj Gupta, Sandeep Sen |
| 2011 | Rounding Semidefinite Programming Hierarchies via Global Correlation. | Boaz Barak, Prasad Raghavendra, David Steurer |
| 2011 | Min-max Graph Partitioning and Small Set Expansion. | Nikhil Bansal, Uriel Feige, Robert Krauthgamer, Konstantin Makarychev, Viswanath Nagarajan, Joseph Naor, Roy Schwartz |
| 2011 | A Polylogarithmic-Competitive Algorithm for the k-Server Problem. | Nikhil Bansal, Niv Buchbinder, Aleksander Madry, Joseph Naor |
| 2011 | How to Garble Arithmetic Circuits. | Benny Applebaum, Yuval Ishai, Eyal Kushilevitz |
| 2011 | Streaming Algorithms via Precision Sampling. | Alexandr Andoni, Robert Krauthgamer, Krzysztof Onak |
| 2011 | Near Linear Lower Bound for Dimension Reduction in L1. | Alexandr Andoni, Moses Charikar, Ofer Neiman, Huy L. Nguyen |
| 2011 | The Complexity of Renaming. | Dan Alistarh, James Aspnes, Seth Gilbert, Rachid Guerraoui |
| 2011 | Bayesian Combinatorial Auctions: Expanding Single Buyer Mechanisms to Many Buyers. | Saeed Alaei |
| 2011 | On the Complexity of Commuting Local Hamiltonians, and Tight Conditions for Topological Order in Such Systems. | Dorit Aharonov, Lior Eldar |
| 2011 | The 1D Area Law and the Complexity of Quantum States: A Combinatorial Approach. | Dorit Aharonov, Itai Arad, Zeph Landau, Umesh V. Vazirani |
| 2010 | Agnostically Learning under Permutation Invariant Distributions. | Karl Wimmer |
| 2010 | Subcubic Equivalences between Path, Matrix and Triangle Problems. | Virginia Vassilevska Williams, Ryan Williams |
| 2010 | Replacement Paths via Fast Matrix Multiplication. | Oren Weimann, Raphael Yuster |