| 2009 | A Comparison of Techniques for Sampling Web Pages. Eda Baykan, Monika Henzinger, Stefan F. Keller, Sebastian De Castelberg, Markus Kinzler |
| 2009 | A Complexity Dichotomy for Partition Functions with Mixed Signs. Leslie Ann Goldberg, Martin Grohe, Mark Jerrum, Marc Thurley |
| 2009 | A Generalization of Nemhauser and Trotter's Local Optimization Theorem. Michael R. Fellows, Jiong Guo, Hannes Moser, Rolf Niedermeier |
| 2009 | A Polynomial Kernel for Multicut in Trees. Nicolas Bousquet, Jean Daligault, Stéphan Thomassé, Anders Yeo |
| 2009 | A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints. Kenya Ueno |
| 2009 | A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression. Danny Hermelin, Gad M. Landau, Shir Landau, Oren Weimann |
| 2009 | Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties. Mahdi Cheraghchi, Amin Shokrollahi |
| 2009 | Ambiguity and Communication. Juraj Hromkovic, Georg Schnitger |
| 2009 | An Approximation Algorithm for l Victor Chepoi, Morgan Seston |
| 2009 | An Order on Sets of Tilings Corresponding to an Order on Languages. Nathalie Aubrun, Mathieu Sablik |
| 2009 | Approximating Acyclicity Parameters of Sparse Hypergraphs. Fedor V. Fomin, Petr A. Golovach, Dimitrios M. Thilikos |
| 2009 | Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness. André Gronemeier |
| 2009 | Büchi Complementation Made Tight. Sven Schewe |
| 2009 | Compressed Representations of Permutations, and Applications. Jérémy Barbay, Gonzalo Navarro |
| 2009 | Computing Graph Roots Without Short Cycles. Babak Farzad, Lap Chi Lau, Van Bang Le, Nguyen Ngoc Tuy |
| 2009 | Cover Time and Broadcast Time. Robert Elsässer, Thomas Sauerwald |
| 2009 | Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata. Daniel Kirsten, Sylvain Lombardy |
| 2009 | Economical Caching. Matthias Englert, Heiko Röglin, Jacob Spönemann, Berthold Vöcking |
| 2009 | Efficient Isomorphism Testing for a Class of Group Extensions. François Le Gall |
| 2009 | Enumerating Homomorphisms. Andrei A. Bulatov, Víctor Dalmau, Martin Grohe, Dániel Marx |
| 2009 | Equations over Sets of Natural Numbers with Addition Only. Artur Jez, Alexander Okhotin |
| 2009 | Error-Correcting Data Structures. Ronald de Wolf |
| 2009 | Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence. Marius Zimand |
| 2009 | Forward Analysis for WSTS, Part I: Completions. Alain Finkel, Jean Goubault-Larrecq |
| 2009 | Fragments of First-Order Logic over Infinite Words. Volker Diekert, Manfred Kufleitner |
| 2009 | Generating Shorter Bases for Hard Random Lattices. Joël Alwen, Chris Peikert |
| 2009 | Hardness and Algorithms for Rainbow Connectivity. Sourav Chakraborty, Eldar Fischer, Arie Matsliah, Raphael Yuster |
| 2009 | Improved Approximations for Guarding 1.5-Dimensional Terrains. Khaled M. Elbassioni, Erik Krohn, Domagoj Matijevic, Julián Mestre, Domagoj Severdija |
| 2009 | Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves. Henning Fernau, Fedor V. Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh, Yngve Villanger |
| 2009 | Kolmogorov Complexity and Solovay Functions. Laurent Bienvenu, Rod Downey |
| 2009 | Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time. Fabian Kuhn |
| 2009 | Locally Decodable Quantum Codes. Jop Briët, Ronald de Wolf |
| 2009 | Lower Bounds for Multi-Pass Processing of Multiple Data Streams. Nicole Schweikardt |
| 2009 | More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries. Roberto Grossi, Alessio Orlandi, Rajeev Raman, S. Srinivasa Rao |
| 2009 | Nonclairvoyant Speed Scaling for Flow and Energy. Ho-Leung Chan, Jeff Edmonds, Tak Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela, Kirk Pruhs |
| 2009 | On Approximating Multi-Criteria TSP. Bodo Manthey |
| 2009 | On Local Symmetries and Universality in Cellular Automata. Laurent Boyer, Guillaume Theyssier |
| 2009 | On the Average Complexity of Moore's State Minimization Algorithm. Frédérique Bassino, Julien David, Cyril Nicaud |
| 2009 | On the Borel Inseparability of Game Tree Languages. Szczepan Hummel, Henryk Michalewski, Damian Niwinski |
| 2009 | Optimal Cache-Aware Suffix Selection. Gianni Franceschini, Roberto Grossi, S. Muthukrishnan |
| 2009 | Polynomial Kernelizations for MIN F Stefan Kratsch |
| 2009 | Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs. Glencora Borradaile, Erik D. Demaine, Siamak Tazari |
| 2009 | Preface - 26th International Symposium on Theoretical Aspects of Computer Science. Susanne Albers, Jean-Yves Marion |
| 2009 | Proceedings of the 26th International Symposium on Theoretical Aspects of Computer Science, STACS 2009, Freiburg, Germany, February 26-28, 2009 Susanne Albers, Jean-Yves Marion |
| 2009 | Profinite Methods in Automata Theory. Jean-Eric Pin |
| 2009 | Qualitative Reachability in Stochastic BPA Games. Tomás Brázdil, Václav Brozek, Antonín Kucera, Jan Obdrzálek |
| 2009 | Quantum Query Complexity of Multilinear Identity Testing. Vikraman Arvind, Partha Mukhopadhyay |
| 2009 | Random Fruits on the Zielonka Tree. Florian Horn |
| 2009 | Randomness on Computable Probability Spaces - A Dynamical Point of View. Péter Gács, Mathieu Hoyrup, Cristobal Rojas |
| 2009 | Reverse Engineering Prefix Tables. Julien Clément, Maxime Crochemore, Giuseppina Rindone |
| 2009 | Semi-Online Preemptive Scheduling: One Algorithm for All Variants. Tomás Ebenlendr, Jirí Sgall |
| 2009 | Shortest Paths Avoiding Forbidden Subpaths. Mustaq Ahmed, Anna Lubiw |
| 2009 | Strong Completeness of Coalgebraic Modal Logics. Lutz Schröder, Dirk Pattinson |
| 2009 | Testing Linear-Invariant Non-Linear Properties. Arnab Bhattacharyya, Victor Chen, Madhu Sudan, Ning Xie |
| 2009 | The Dynamic Complexity of Formal Languages. Wouter Gelade, Marcel Marquardt, Thomas Schwentick |
| 2009 | The Price of Anarchy in Cooperative Network Creation Games. Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini, Morteza Zadimoghaddam |
| 2009 | Tractable Structures for Constraint Satisfaction with Truth Tables. Dániel Marx |
| 2009 | Undecidable Properties of Limit Set Dynamics of Cellular Automata. Pietro di Lena, Luciano Margara |
| 2009 | Weak MSO with the Unbounding Quantifier. Mikolaj Bojanczyk |