| 2010 | Zero-one frequency laws. | Vladimir Braverman, Rafail Ostrovsky |
| 2010 | Measuring independence of datasets. | Vladimir Braverman, Rafail Ostrovsky |
| 2010 | Budget constrained auctions with heterogeneous items. | Sayan Bhattacharya, Gagan Goel, Sreenivas Gollapudi, Kamesh Munagala |
| 2010 | Detecting high log-densities: an | Aditya Bhaskara, Moses Charikar, Eden Chlamtac, Uriel Feige, Aravindan Vijayaraghavan |
| 2010 | Hardness amplification in proof complexity. | Paul Beame, Trinh Huynh, Toniann Pitassi |
| 2010 | Combinatorial approach to the interpolation method and scaling limits in sparse random graphs. | Mohsen Bayati, David Gamarnik, Prasad Tetali |
| 2010 | Approximation schemes for steiner forest on planar graphs and graphs of bounded treewidth. | MohammadHossein Bateni, MohammadTaghi Hajiaghayi, Dniel Marx |
| 2010 | How to compress interactive communication. | Boaz Barak, Mark Braverman, Xi Chen, Anup Rao |
| 2010 | On the hardness of the noncommutative determinant. | Vikraman Arvind, Srikanth Srinivasan |
| 2010 | Public-key cryptography from different assumptions. | Benny Applebaum, Boaz Barak, Avi Wigderson |
| 2010 | A quantum lovsz local lemma. | Andris Ambainis, Julia Kempe, Or Sattath |
| 2010 | Erratum for: on basing one-way functions on NP-hardness. | Adi Akavia, Oded Goldreich, Shafi Goldwasser, Dana Moshkovitz |
| 2010 | Oblivious RAMs without cryptogrpahic assumptions. | Mikls Ajtai |
| 2010 | A full characterization of quantum advice. | Scott Aaronson, Andrew Drucker |
| 2010 | BQP and the polynomial hierarchy. | Scott Aaronson |
| 2009 | An improved constant-time approximation algorithm for maximum matchings. | Yuichi Yoshida, Masaki Yamamoto, Hiro Ito |
| 2009 | The work of Leslie Valiant. | Avi Wigderson |
| 2009 | Bit-probe lower bounds for succinct data structures. | Emanuele Viola |
| 2009 | Finding, minimizing, and counting weighted subgraphs. | Virginia Vassilevska, Ryan Williams |
| 2009 | CSP gaps and reductions in the lasserre hierarchy. | Madhur Tulsiani |
| 2009 | Max cut and the smallest eigenvalue. | Luca Trevisan |
| 2009 | Short seed extractors against quantum storage. | Amnon Ta-Shma |
| 2009 | Reconstruction for the Potts model. | Allan Sly |
| 2009 | Green's conjecture and testing linear-invariant properties. | Asaf Shapira |
| 2009 | Exact learning of random DNF over the uniform distribution. | Linda Sellie |