| 2009 | Algorithms for finding an induced cycle in planar graphs and bounded genus graphs. | Yusuke Kobayashi, Ken-ichi Kawarabayashi |
| 2009 | Shortest paths in directed planar graphs with negative lengths: a linear-space | Philip N. Klein, Shay Mozes, Oren Weimann |
| 2009 | A nearly linear time algorithm for the half integral parity disjoint paths packing problem. | Ken-ichi Kawarabayashi, Bruce A. Reed |
| 2009 | List-color-critical graphs on a fixed surface. | Ken-ichi Kawarabayashi, Bojan Mohar |
| 2009 | Additive approximation algorithms for list-coloring minor-closed class of graphs. | Ken-ichi Kawarabayashi, Erik D. Demaine, MohammadTaghi Hajiaghayi |
| 2009 | A near-linear time algorithm for constructing a cactus representation of minimum cuts. | David R. Karger, Debmalya Panigrahi |
| 2009 | A simpler implementation and analysis of Chazelle's soft heaps. | Haim Kaplan, Uri Zwick |
| 2009 | Line transversals of convex polyhedra in | Haim Kaplan, Natan Rubin, Micha Sharir |
| 2009 | Combinatorial stochastic processes and nonparametric Bayesian modeling. | Michael I. Jordan |
| 2009 | The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite. | William B. Johnson, Assaf Naor |
| 2009 | Parameterized approximation scheme for the multiple knapsack problem. | Klaus Jansen |
| 2009 | A simple combinatorial algorithm for submodular function minimization. | Satoru Iwata, James B. Orlin |
| 2009 | Size complexity of volume meshes vs. surface meshes. | Benot Hudson, Gary L. Miller, Todd Phillips, Don Sheehy |
| 2009 | How hard is it to approximate the best Nash equilibrium? | Elad Hazan, Robert Krauthgamer |
| 2009 | Better algorithms for benign bandits. | Elad Hazan, Satyen Kale |
| 2009 | Approximation algorithms for restless bandit problems. | Sudipto Guha, Kamesh Munagala, Peng Shi |
| 2009 | Sampling biased lattice configurations using exponential metrics. | Sam Greenberg, Amanda Pascoe, Dana Randall |
| 2009 | Expanders via random spanning trees. | Navin Goyal, Luis Rademacher, Santosh S. Vempala |
| 2009 | Finding duplicates in a data stream. | Parikshit Gopalan, Jaikumar Radhakrishnan |
| 2009 | Cell probe lower bounds for succinct data structures. | Alexander Golynski |
| 2009 | A generic top-down dynamic-programming approach to prefix-free coding. | Mordecai J. Golin, Xiaoming Xu, Jiajin Yu |
| 2009 | Approximating submodular functions everywhere. | Michel X. Goemans, Nicholas J. A. Harvey, Satoru Iwata, Vahab S. Mirrokni |
| 2009 | The ratio index for budgeted learning, with applications. | Ashish Goel, Sanjeev Khanna, Brad Null |
| 2009 | Perfect matchings via uniform sampling in regular bipartite graphs. | Ashish Goel, Michael Kapralov, Sanjeev Khanna |
| 2009 | A universally fastest algorithm for Max 2-Sat, Max 2-CSP, and everything in between. | Serge Gaspers, Gregory B. Sorkin |