| 2009 | Efficient algorithms for the 2-gathering problem. | Alon Shalita, Uri Zwick |
| 2009 | Optimality of belief propagation for random assignment problem. | J. Salez, D. Shah |
| 2009 | Stepwise randomized combinatorial auctions achieve revenue monotonicity. | Baharak Rastegari, Anne Condon, Kevin Leyton-Brown |
| 2009 | Towards computing the Grothendieck constant. | Prasad Raghavendra, David Steurer |
| 2009 | Exponential lower bounds and integrality gaps for tree-like Lovsz-Schrijver procedures. | Toniann Pitassi, Nathan Segerlind |
| 2009 | Almost all hypergraphs without Fano planes are bipartite. | Yury Person, Mathias Schacht |
| 2009 | The unreasonable effectiveness of martingales. | Yuval Peres |
| 2009 | Maximal biconnected subgraphs of random planar graphs. | Konstantinos Panagiotou, Angelika Steger |
| 2009 | 3-bit dictator testing: 1 vs. 5/8. | Ryan O'Donnell, Yi Wu |
| 2009 | An almost | Zeev Nutov |
| 2009 | Improved bounds and new techniques for Davenport-Schinzel sequences and their generalizations. | Gabriel Nivasch |
| 2009 | Hypergraph regularity and quasi-randomness. | Brendan Nagle, Annika Poerschke, Vojtech Rdl, Mathias Schacht |
| 2009 | On the maximum quadratic assignment problem. | Viswanath Nagarajan, Maxim Sviridenko |
| 2009 | Asymptotically optimal frugal colouring. | Michael Molloy, Bruce A. Reed |
| 2009 | The extended | Lorenz Minder, Alistair Sinclair |
| 2009 | Testing halfspaces. | Kevin Matulef, Ryan O'Donnell, Ronitt Rubinfeld, Rocco A. Servedio |
| 2009 | Hardness of embedding simplicial complexes in | Jir Matousek, Martin Tancer, Uli Wagner |
| 2009 | Approximating fractional hypertree width. | Dniel Marx |
| 2009 | Improved smoothed analysis of the | Bodo Manthey, Heiko Rglin |
| 2009 | On the hitting times of quantum versus random walks. | Frdric Magniez, Ashwin Nayak, Peter C. Richter, Miklos Santha |
| 2009 | Discounted deterministic Markov decision processes and discounted all-pairs shortest paths. | Omid Madani, Mikkel Thorup, Uri Zwick |
| 2009 | Combinatorial algorithms for nearest neighbors, near-duplicates and small-world design. | Yury Lifshits, Shengyu Zhang |
| 2009 | Compressed counting. | Ping Li |
| 2009 | Maximizing submodular set functions subject to multiple linear constraints. | Ariel Kulik, Hadas Shachnai, Tami Tamir |
| 2009 | Partitioning graphs into balanced components. | Robert Krauthgamer, Joseph Naor, Roy Schwartz |