| 2009 | Intrinsic robustness of the price of anarchy. | Tim Roughgarden |
| 2009 | Explicit construction of a small epsilon-net for linear threshold functions. | Yuval Rabani, Amir Shpilka |
| 2009 | Public-key cryptosystems from the worst-case shortest vector problem: extended abstract. | Chris Peikert |
| 2009 | Conditional hardness for satisfiable 3-CSPs. | Ryan O'Donnell, Yi Wu |
| 2009 | A fast and efficient algorithm for low-rank approximation of a matrix. | Nam H. Nguyen, Thong T. Do, Trac D. Tran |
| 2009 | A constructive proof of the Lovsz local lemma. | Robin A. Moser |
| 2009 | How long does it take to catch a wild kangaroo? | Ravi Montenegro, Prasad Tetali |
| 2009 | Sherali-adams relaxations of the matching polytope. | Claire Mathieu, Alistair Sinclair |
| 2009 | Mixing time for the solid-on-solid model. | Fabio Martinelli, Alistair Sinclair |
| 2009 | Quantum algorithms using the curvelet transform. | Yi-Kai Liu |
| 2009 | A unified framework for concurrent security: universal composability from stand-alone non-malleability. | Huijia Lin, Rafael Pass, Muthuramakrishnan Venkitasubramaniam |
| 2009 | Non-malleability amplification. | Huijia Lin, Rafael Pass |
| 2009 | On the geometry of graphs with a forbidden minor. | James R. Lee, Anastasios Sidiropoulos |
| 2009 | Non-monotone submodular maximization under matroid and knapsack constraints. | Jon Lee, Vahab S. Mirrokni, Viswanath Nagarajan, Maxim Sviridenko |
| 2009 | Affiliation networks. | Silvio Lattanzi, D. Sivakumar |
| 2009 | On the complexity of communication complexity. | Eyal Kushilevitz, Enav Weinreb |
| 2009 | A new line of attack on the dichotomy conjecture. | Gbor Kun, Mario Szegedy |
| 2009 | Random graphs and the parity quantifier. | Phokion G. Kolaitis, Swastik Kopparty |
| 2009 | Multiplicative updates outperform generic no-regret learning in congestion games: extended abstract. | Robert Kleinberg, Georgios Piliouras, va Tardos |
| 2009 | Hadwiger's conjecture is decidable. | Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2009 | Linear time approximation schemes for the Gale-Berlekamp game and related minimization problems. | Marek Karpinski, Warren Schudy |
| 2009 | Random walks on polytopes and an affine interior point method for linear programming. | Ravi Kannan, Hariharan Narayanan |
| 2009 | New direct-product testers and 2-query PCPs. | Russell Impagliazzo, Valentine Kabanets, Avi Wigderson |
| 2009 | An axiomatic approach to algebrization. | Russell Impagliazzo, Valentine Kabanets, Antonina Kolokolova |
| 2009 | Inaccessible entropy. | Iftach Haitner, Omer Reingold, Salil P. Vadhan, Hoeteck Wee |