| 2009 | Blackbox Polynomial Identity Testing for Depth 3 Circuits. | Neeraj Kayal, Shubhangi Saraf |
| 2009 | Planarity Allowing Few Error Vertices in Linear Time. | Ken-ichi Kawarabayashi |
| 2009 | A New Probability Inequality Using Typical Moments and Concentration Results. | Ravindran Kannan |
| 2009 | The Complexity of Rationalizing Network Formation. | Shankar Kalyanaraman, Christopher Umans |
| 2009 | Learning and Smoothed Analysis. | Adam Tauman Kalai, Alex Samorodnitsky, Shang-Hua Teng |
| 2009 | 2-Source Extractors under Computational Assumptions and Cryptography with Defective Randomness. | Yael Tauman Kalai, Xin Li, Anup Rao |
| 2009 | The Data Stream Space Complexity of Cascaded Norms. | T. S. Jayram, David P. Woodruff |
| 2009 | Two-Message Quantum Interactive Proofs Are in PSPACE. | Rahul Jain, Sarvagya Upadhyay, John Watrous |
| 2009 | Submodular Function Minimization under Covering Constraints. | Satoru Iwata, Kiyohito Nagano |
| 2009 | Extracting Correlations. | Yuval Ishai, Eyal Kushilevitz, Rafail Ostrovsky, Amit Sahai |
| 2009 | Space-Efficient Framework for Top-k String Retrieval Problems. | Wing-Kai Hon, Rahul Shah, Jeffrey Scott Vitter |
| 2009 | Local Graph Partitions for Approximation and Testing. | Avinatan Hassidim, Jonathan A. Kelner, Huy N. Nguyen, Krzysztof Onak |
| 2009 | A Parallel Repetition Theorem for Any Interactive Argument. | Iftach Haitner |
| 2009 | The Quantum and Classical Complexity of Translationally Invariant Tiling and Hamiltonian Problems. | Daniel Gottesman, Sandy Irani |
| 2009 | An Oblivious O(1)-Approximation for Single Source Buy-at-Bulk. | Ashish Goel, Ian Post |
| 2009 | Approximability of Combinatorial Problems with Multi-agent Submodular Cost Functions. | Gagan Goel, Chinmay Karande, Pushkar Tripathi, Lei Wang |
| 2009 | Decomposing Coverings and the Planar Sensor Cover Problem. | Matt Gibson, Kasturi R. Varadarajan |
| 2009 | Online Stochastic Matching: Beating 1-1/e. | Jon Feldman, Aranyak Mehta, Vahab S. Mirrokni, S. Muthukrishnan |
| 2009 | Agnostic Learning of Monomials by Halfspaces Is Hard. | Vitaly Feldman, Venkatesan Guruswami, Prasad Raghavendra, Yi Wu |
| 2009 | A Complete Characterization of Statistical Query Learning with Applications to Evolvability. | Vitaly Feldman |
| 2009 | Oblivious Routing for the Lp-norm. | Matthias Englert, Harald Rcke |
| 2009 | Extensions to the Method of Multiplicities, with Applications to Kakeya Sets and Mergers. | Zeev Dvir, Swastik Kopparty, Shubhangi Saraf, Madhu Sudan |
| 2009 | Randomized Self-Assembly for Exact Shapes. | David Doty |
| 2009 | On the Power of Randomization in Algorithmic Mechanism Design. | Shahar Dobzinski, Shaddin Dughmi |
| 2009 | Composition of Low-Error 2-Query PCPs Using Decodable PCPs. | Irit Dinur, Prahladh Harsha |