| 2009 | Dynamic Succinct Ordered Trees. | Arash Farzan, J. Ian Munro |
| 2009 | Improved Algorithms for Latency Minimization in Wireless Networks. | Alexander Fanghnel, Thomas Keelheim, Berthold Vcking |
| 2009 | Online Computation with Advice. | Yuval Emek, Pierre Fraigniaud, Amos Korman, Adi Rosn |
| 2009 | Tight Bounds for the Cover Time of Multiple Random Walks. | Robert Elssser, Thomas Sauerwald |
| 2009 | High Complexity Tilings with Sparse Errors. | Bruno Durand, Andrei Romashchenko, Alexander Shen |
| 2009 | Partition Arguments in Multiparty Communication Complexity. | Jan Draisma, Eyal Kushilevitz, Enav Weinreb |
| 2009 | Incompressibility through Colors and IDs. | Michael Dom, Daniel Lokshtanov, Saket Saurabh |
| 2009 | Quasirandom Rumor Spreading: Expanders, Push vs. Pull, and Robustness. | Benjamin Doerr, Tobias Friedrich, Thomas Sauerwald |
| 2009 | Applications of a Splitting Trick. | Martin Dietzfelbinger, Michael Rink |
| 2009 | On Cartesian Trees and Range Minimum Queries. | Erik D. Demaine, Gad M. Landau, Oren Weimann |
| 2009 | Node-Weighted Steiner Tree and Group Steiner Tree in Planar Graphs. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Philip N. Klein |
| 2009 | Approximation Algorithms via Structural Results for Apex-Minor-Free Graphs. | Erik D. Demaine, MohammadTaghi Hajiaghayi, Ken-ichi Kawarabayashi |
| 2009 | On Regular Temporal Logics with Past, . | Christian Dax, Felix Klaedtke, Martin Lange |
| 2009 | On a Network Generalization of the Minmax Theorem. | Constantinos Daskalakis, Christos H. Papadimitriou |
| 2009 | Exact and Approximate Bandwidth. | Marek Cygan, Marcin Pilipczuk |
| 2009 | Derandomizing Random Walks in Undirected Graphs Using Locally Fair Exploration Strategies. | Colin Cooper, David Ilcinkas, Ralf Klasing, Adrian Kosowski |
| 2009 | Multiple Random Walks and Interacting Particle Systems. | Colin Cooper, Alan M. Frieze, Tomasz Radzik |
| 2009 | A Tight Lower Bound for Determinization of Transition Labeled Bchi Automata. | Thomas Colcombet, Konrad Zdanowski |
| 2009 | The Theory of Stabilisation Monoids and Regular Cost Functions. | Thomas Colcombet |
| 2009 | A Better Algorithm for Random | Amin Coja-Oghlan |
| 2009 | MANETS: High Mobility Can Make Up for Low Transmission Power. | Andrea E. F. Clementi, Francesco Pasquale, Riccardo Silvestri |
| 2009 | Rumor Spreading in Social Networks. | Flavio Chierichetti, Silvio Lattanzi, Alessandro Panconesi |
| 2009 | Strong and Pareto Price of Anarchy in Congestion Games. | Steve Chien, Alistair Sinclair |
| 2009 | Approximating Matches Made in Heaven. | Ning Chen, Nicole Immorlica, Anna R. Karlin, Mohammad Mahdian, Atri Rudra |
| 2009 | A Graph Reduction Step Preserving Element-Connectivity and Applications. | Chandra Chekuri, Nitish Korula |