| 2009 | Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. | Marius Zimand |
| 2009 | Error-Correcting Data Structures. | Ronald de Wolf |
| 2009 | A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints. | Kenya Ueno |
| 2009 | Lower Bounds for Multi-Pass Processing of Multiple Data Streams. | Nicole Schweikardt |
| 2009 | Strong Completeness of Coalgebraic Modal Logics. | Lutz Schrder, Dirk Pattinson |
| 2009 | Bchi Complementation Made Tight. | Sven Schewe |
| 2009 | Profinite Methods in Automata Theory. | Jean-Eric Pin |
| 2009 | Tractable Structures for Constraint Satisfaction with Truth Tables. | Dniel Marx |
| 2009 | On Approximating Multi-Criteria TSP. | Bodo Manthey |
| 2009 | Undecidable Properties of Limit Set Dynamics of Cellular Automata. | Pietro di Lena, Luciano Margara |
| 2009 | Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time. | Fabian Kuhn |
| 2009 | Polynomial Kernelizations for MIN F | Stefan Kratsch |
| 2009 | Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. | Daniel Kirsten, Sylvain Lombardy |
| 2009 | Equations over Sets of Natural Numbers with Addition Only. | Artur Jez, Alexander Okhotin |
| 2009 | On the Borel Inseparability of Game Tree Languages. | Szczepan Hummel, Henryk Michalewski, Damian Niwinski |
| 2009 | Ambiguity and Communication. | Juraj Hromkovic, Georg Schnitger |
| 2009 | Random Fruits on the Zielonka Tree. | Florian Horn |
| 2009 | A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. | Danny Hermelin, Gad M. Landau, Shir Landau, Oren Weimann |
| 2009 | More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. | Roberto Grossi, Alessio Orlandi, Rajeev Raman, S. Srinivasa Rao |
| 2009 | Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. | Andr Gronemeier |
| 2009 | A Complexity Dichotomy for Partition Functions with Mixed Signs. | Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley |
| 2009 | The Dynamic Complexity of Formal Languages. | Wouter Gelade, Marcel Marquardt, Thomas Schwentick |
| 2009 | Efficient Isomorphism Testing for a Class of Group Extensions. | Franois Le Gall |
| 2009 | Randomness on Computable Probability Spaces - A Dynamical Point of View. | Pter Gcs, Mathieu Hoyrup, Cristobal Rojas |
| 2009 | Optimal Cache-Aware Suffix Selection. | Gianni Franceschini, Roberto Grossi, S. Muthukrishnan |