| 2009 | Complexity of Model Checking Recursion Schemes for Fragments of the Modal Mu-Calculus. | Naoki Kobayashi, C.-H. Luke Ong |
| 2009 | General Scheme for Perfect Quantum Network Coding with Free Classical Communication. | Hirotada Kobayashi, Franois Le Gall, Harumichi Nishimura, Martin Rtteler |
| 2009 | Learning Halfspaces with Malicious Noise. | Adam R. Klivans, Philip M. Long, Rocco A. Servedio |
| 2009 | On Finding Dense Subgraphs. | Samir Khuller, Barna Saha |
| 2009 | Factoring Groups Efficiently. | Neeraj Kayal, Timur Nezhmetdinov |
| 2009 | Popular Mixed Matchings. | Telikepalli Kavitha, Julin Mestre, Meghana Nasre |
| 2009 | Diagrammatic Confluence and Completion. | Jean-Pierre Jouannaud, Vincent van Oostrom |
| 2009 | An EPTAS for Scheduling Jobs on Uniform Processors: Using an MILP Relaxation with a Constant Number of Integral Variables. | Klaus Jansen |
| 2009 | Secure Function Collection with Sublinear Storage. | Maged H. Ibrahim, Aggelos Kiayias, Moti Yung, Hong-Sheng Zhou |
| 2009 | Applications of Effective Probability Theory to Martin-Lf Randomness. | Mathieu Hoyrup, Cristobal Rojas |
| 2009 | The Ehrenfeucht-Silberger Problem. | Stepan Holub, Dirk Nowotka |
| 2009 | Wireless Communication Is in APX. | Magns M. Halldrsson, Roger Wattenhofer |
| 2009 | Multi-armed Bandits with Metric Switching Costs. | Sudipto Guha, Kamesh Munagala |
| 2009 | Revisiting the Direct Sum Theorem and Space Lower Bounds in Random Order Streams. | Sudipto Guha, Zhiyi Huang |
| 2009 | Names Trump Malice: Tiny Mobile Agents Can Tolerate Byzantine Failures. | Rachid Guerraoui, Eric Ruppert |
| 2009 | Qualitative Concurrent Stochastic Games with Imperfect Information. | Vincent Gripon, Olivier Serre |
| 2009 | Tractable Optimization Problems through Hypergraph-Based Structural Restrictions. | Georg Gottlob, Gianluigi Greco, Francesco Scarcello |
| 2009 | Testing Fourier Dimensionality and Sparsity. | Parikshit Gopalan, Ryan O'Donnell, Rocco A. Servedio, Amir Shpilka, Karl Wimmer |
| 2009 | B-Treaps: A Uniquely Represented Alternative to B-Trees. | Daniel Golovin |
| 2009 | Towards Optimal Range Medians. | Beat Gfeller, Peter Sanders |
| 2009 | Smoothed Analysis of Balancing Networks. | Tobias Friedrich, Thomas Sauerwald, Dan Vilenchik |
| 2009 | Efficient Methods for Selfish Network Design. | Dimitris Fotakis, Alexis C. Kaporis, Paul G. Spirakis |
| 2009 | Forward Analysis for WSTS, Part II: Complete WSTS. | Alain Finkel, Jean Goubault-Larrecq |
| 2009 | Distortion Is Fixed Parameter Tractable. | Michael R. Fellows, Fedor V. Fomin, Daniel Lokshtanov, Elena Losievskaja, Frances A. Rosamond, Saket Saurabh |
| 2009 | Universal Succinct Representations of Trees? | Arash Farzan, Rajeev Raman, S. Srinivasa Rao |