| 2009 | Quantum Algorithms to Solve the Hidden Shift Problem for Quadratics and for Functions of Large Gowers Norm. | Martin Rtteler |
| 2009 | (Un)Decidability of Injectivity and Surjectivity in One-Dimensional Sand Automata. | Gatan Richard |
| 2009 | Points on Computable Curves of Computable Lengths. | Robert Rettinger, Xizhong Zheng |
| 2009 | The Cost of Stability in Network Flow Games. | Ezra Resnick, Yoram Bachrach, Reshef Meir, Jeffrey S. Rosenschein |
| 2009 | A Probabilistic PTAS for Shortest Common Superstring. | Kai Plociennik |
| 2009 | On the Structure of Optimal Greedy Computation (for Job Scheduling). | Periklis A. Papakonstantinou |
| 2009 | Colouring Non-sparse Random Intersection Graphs. | Sotiris E. Nikoletseas, Christoforos L. Raptopoulos, Paul G. Spirakis |
| 2009 | Stochastic Data Streams. | S. Muthukrishnan |
| 2009 | The Complexity of Satisfiability for Fragments of Hybrid Logic-Part I. | Arne Meier, Martin Mundhenk, Thomas Schneider, Michael Thomas, Volker Weber, Felix Weiss |
| 2009 | A General Class of Models of H | Giulio Manzonetto |
| 2009 | Query Automata for Nested Words. | P. Madhusudan, Mahesh Viswanathan |
| 2009 | Snake-Deterministic Tiling Systems. | Violetta Lonati, Matteo Pradella |
| 2009 | On FO2 Quantifier Alternation over Words. | Manfred Kufleitner, Pascal Weil |
| 2009 | Graph Decomposition for Improving Memoryless Periodic Exploration. | Adrian Kosowski, Alfredo Navarra |
| 2009 | The Isomorphism Problem for k-Trees Is Complete for Logspace. | Johannes Kbler, Sebastian Kuhnert |
| 2009 | An Algebraic Characterization of Semirings for Which the Support of Every Recognizable Series Is Recognizable. | Daniel Kirsten |
| 2009 | A Dynamic Algorithm for Reachability Games Played on Trees. | Bakhadyr Khoussainov, Jiamou Liu, Imran Khaliq |
| 2009 | The Prismoid of Resources. | Delia Kesner, Fabien Renaud |
| 2009 | FO Model Checking on Nested Pushdown Trees. | Alexander Kartzow |
| 2009 | On the Recognizability of Self-generating Sets. | Tomi Krki, Anne Lacroix, Michel Rigo |
| 2009 | Bounds on Non-surjective Cellular Automata. | Jarkko Kari, Pascal Vanier, Thomas Zeume |
| 2009 | On the Hybrid Extension of CTL and CTL | Ahmet Kara, Volker Weber, Martin Lange, Thomas Schwentick |
| 2009 | Synthesis for Structure Rewriting Systems. | Lukasz Kaiser |
| 2009 | The Longest Path Problem Is Polynomial on Interval Graphs. | Kyriaki Ioannidou, George B. Mertzios, Stavros D. Nikolopoulos |
| 2009 | Time-Bounded Kolmogorov Complexity and Solovay Functions. | Rupert Hlzl, Thorsten Krling, Wolfgang Merkle |