| 2009 | The Complexity of Nash Equilibria in Simple Stochastic Multiplayer Games. | Michael Ummels, Dominik Wojtczak |
| 2009 | A Distributed and Oblivious Heap. | Christian Scheideler, Stefan Schmid |
| 2009 | Amortized Communication Complexity of Distributions. | Jrmie Roland, Mario Szegedy |
| 2009 | On Observing Dynamic Prioritised Actions in SOC. | Rosario Pugliese, Francesco Tiezzi, Nobuko Yoshida |
| 2009 | A Decidable Characterization of Locally Testable Tree Languages. | Thomas Place, Luc Segoufin |
| 2009 | Weak Alternating Timed Automata. | Pawel Parys, Igor Walukiewicz |
| 2009 | Algorithmic Game Theory: A Snapshot. | Christos H. Papadimitriou |
| 2009 | Google's Auction for TV Ads. | Noam Nisan, Jason Bayer, Deepak Chandra, Tal Franji, Robert Gardner, Yossi Matias, Neil Rhodes, Misha Seltzer, Danny Tom, Hal R. Varian, Dan Zigmond |
| 2009 | Superhighness and Strong Jump Traceability. | Andr Nies |
| 2009 | Rate-Based Transition Systems for Stochastic Process Calculi. | Rocco De Nicola, Diego Latella, Michele Loreti, Mieke Massink |
| 2009 | Fast Polynomial-Space Algorithms Using Mbius Inversion: Improving on Steiner Tree and Related Problems. | Jesper Nederlof |
| 2009 | Worst-Case Efficiency Analysis of Queueing Disciplines. | Damon Mosk-Aoyama, Tim Roughgarden |
| 2009 | Limiting Negations in Formulas. | Hiroki Morizumi |
| 2009 | Decidability of the Guarded Fragment with the Transitive Closure. | Jakub Michaliszyn |
| 2009 | An Explicit Formula for the Free Exponential Modality of Linear Logic. | Paul-Andr Mellis, Nicolas Tabareau, Christine Tasson |
| 2009 | Assigning Papers to Referees. | Kurt Mehlhorn |
| 2009 | A 3/2-Approximation Algorithm for General Stable Marriage. | Eric McDermid |
| 2009 | Improved Bounds for Flow Shop Scheduling. | Monaldo Mastrolilli, Ola Svensson |
| 2009 | Sleep with Guilt and Work Faster to Minimize Flow Plus Energy. | Tak Wah Lam, Lap-Kei Lee, Hing-Fung Ting, Isaac Kar-Keung To, Prudence W. H. Wong |
| 2009 | On Constructor Rewrite Systems and the Lambda-Calculus. | Ugo Dal Lago, Simone Martini |
| 2009 | LTL Path Checking Is Efficiently Parallelizable. | Lars Kuhtz, Bernd Finkbeiner |
| 2009 | Leader Election in Ad Hoc Radio Networks: A Keen Ear Helps. | Dariusz R. Kowalski, Andrzej Pelc |
| 2009 | Limits and Applications of Group Algebras for Parameterized Problems. | Ioannis Koutis, Ryan Williams |
| 2009 | Greedy D{\ensuremath{\Delta}}-Approximation Algorithm for Covering with Arbitrary Constraints and Submodular Cost. | Christos Koufogiannakis, Neal E. Young |
| 2009 | Algorithms for Secretary Problems on Graphs and Hypergraphs. | Nitish Korula, Martin Pl |