| 2011 | Schaefer's theorem for graphs. | Manuel Bodirsky, Michael Pinsker |
| 2011 | Rank bounds for design matrices with applications toc ombinatorial geometry and locally correctable codes. | Boaz Barak, Zeev Dvir, Amir Yehudayoff, Avi Wigderson |
| 2011 | Learning submodular functions. | Maria-Florina Balcan, Nicholas J. A. Harvey |
| 2011 | Approximate polytope membership queries. | Sunil Arya, Guilherme Dias da Fonseca, David M. Mount |
| 2011 | Secure computation with information leaking to an adversary. | Mikls Ajtai |
| 2011 | Rank-1 bimatrix games: a homeomorphism and a polynomial time algorithm. | Bharat Adsul, Jugal Garg, Ruta Mehta, Milind A. Sohoni |
| 2011 | Almost tight bounds for reordering buffer management. | Anna Adamaszek, Artur Czumaj, Matthias Englert, Harald Rcke |
| 2011 | The computational complexity of linear optics. | Scott Aaronson, Alex Arkhipov |
| 2010 | Improving exhaustive search implies superpolynomial lower bounds. | Ryan Williams |
| 2010 | The limits of buffering: a tight lower bound for dynamic membership in the external memory model. | Elad Verbin, Qin Zhang |
| 2010 | Augmenting undirected node-connectivity by one. | Lszl A. Vgh |
| 2010 | Weighted geometric set cover via quasi-uniform sampling. | Kasturi R. Varadarajan |
| 2010 | Are many small sets explicitly small? | Michel Talagrand |
| 2010 | Conditional hardness of precedence constrained scheduling on identical machines. | Ola Svensson |
| 2010 | Optimal bounds for sign-representing the intersection of two halfspaces by polynomials. | Alexander A. Sherstov |
| 2010 | Interactive privacy via the median mechanism. | Aaron Roth, Tim Roughgarden |
| 2010 | Tensor-rank and lower bounds for arithmetic formulas. | Ran Raz |
| 2010 | Approximations for the isoperimetric and spectral profile of graphs and related parameters. | Prasad Raghavendra, David Steurer, Prasad Tetali |
| 2010 | Graph expansion and the unique games conjecture. | Prasad Raghavendra, David Steurer |
| 2010 | On the complexity of circuit satisfiability. | Ramamohan Paturi, Pavel Pudlk |
| 2010 | Towards polynomial lower bounds for dynamic problems. | Mihai Patrascu |
| 2010 | Improved algorithms for computing fisher's market clearing prices: computing fisher's market clearing prices. | James B. Orlin |
| 2010 | Maintaining a large matching and a small vertex cover. | Krzysztof Onak, Ronitt Rubinfeld |
| 2010 | Message passing algorithms: a success looking for theoreticians. | Andrea Montanari |
| 2010 | A deterministic single exponential time algorithm for most lattice problems based on voronoi cell computations. | Daniele Micciancio, Panagiotis Voulgaris |