List of accepted papers for STACS 2009:


A complexity dichotomy for partition functions with mixed signs
Leslie Ann Goldberg, Martin Grohe, Mark Jerrum and Marc Thurley

Locally Decodable Quantum Codes
Jop Briet and Ronald de Wolf

Ambiguity and Communication
Juraj Hromkovic and Georg Schnitger

Nonclairvoyant Speed Scaling for Flow and Energy
Ho-Leung Chan, Jeff Edmonds, Tak-Wah Lam, Lap-Kei Lee, Alberto Marchetti-Spaccamela and Kirk Pruhs

Error-Correcting Data Structures
Ronald de Wolf

Tractable structures for constraint satisfaction with truth tables
Daniel Marx

A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
Danny Hermelin, Gad Landau, Shir Landau and Oren Weimann

Compressed Representations of Permutations, and Applications
J?r?my Barbay and Gonzalo Navarro

Randomness on Computable Probability Spaces. A Dynamical Point of View
Peter Gacs, Mathieu Hoyrup and Cristobal Rojas

Extracting the Kolmogorov complexity of strings and sequences from sources with limited independence
Marius Zimand

The Price of Anarchy in Cooperative Network Creation Games
Erik D. Demaine, MohammadTaghi Hajiaghayi, Hamid Mahini and Morteza Zadimoghaddam

Undecidable properties of limit set dynamics of Cellular Automata
Pietro Di Lena and Luciano Margara

Polynomial Kernelizations for MIN F+Pi 1 and MAX NP
Stefan Kratsch

Approximating acyclicity parameters of sparse hypergraphs
Fedor Fomin, Petr Golovach and Dimitrios Thilikos

A Stronger LP Bound for Formula Size Lower Bounds via Clique Constraints
Kenya Ueno

Buchi Complementation Made Tight
Sven Schewe

A Generalization of Nemhauser and Trotter's Local Optimization Theorem
Michael Fellows, Jiong Guo, Hannes Moser and Rolf Niedermeier

Strong Completeness of Coalgebraic Modal Logics
Lutz Schr?der and Dirk Pattinson

Testing Linear-Invariant Non-Linear Properties
Arnab Bhattacharyya, Victor Chen, Madhu Sudan and Ning Xie

Efficient Isomorphism Testing for a Class of Group Extensions
Fran?ois Le Gall

Kolmogorov complexity and Solovay functions
Laurent Bienvenu and Rod Downey

On Approximating Multi-Criteria TSP
Bodo Manthey

Fragments of first-order logic over infinite words
Volker Diekert and Manfred Kufleitner

Optimal Cache-Aware Suffix Selection
Gianni Franceschini, Roberto Grossi and S Muthukrishnan

Equations over sets of natural numbers with addition only
Artur Jez and Alexander Okhotin

On the Borel inseparability of game tree languages
Szczepan Hummel, Henryk Michalewski and Damian Niwinski

Generating Shorter Bases for Hard Random Lattices
Joel Alwen and Chris Peikert

An approximation algorithm for l_infinity fitting Robinson structures to distances
Victor Chepoi and Morgan Seston

Improved Approximations for Guarding 1.5-Dimensional Terrains
Khaled Elbassioni, Domagoj Matijevic, Julian Mestre, Domagoj Severdija and Erik Krohn

Economical Caching
Matthias Englert, Heiko Roeglin, Jacob Sp?nemann and Berthold V?cking

Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
Andr? Gronemeier

More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
Roberto Grossi, Alessio Orlandi, Rajeev Raman and Srinivasa Rao Satti

The Dynamic Complexity of Formal Languages
Wouter Gelade, Marcel Marquardt and Thomas Schwentick

Cover Time and Broadcast Time
Robert Els?sser and Thomas Sauerwald

Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties
Mahdi Cheraghchi and Amin Shokrollahi

Semi-Online Preemptive Scheduling: One Algorithm for All Variants
Tom?? Ebenlendr and Jir? Sgall

Quantum Query Complexity of Multilinear Identity Testing
Vikraman Arvind and Partha Mukhopadhyay

Hardness and Algorithms for Rainbow Connectivity
Sourav Chakraborty, Eldar Fischer, Arie Matsliah and Raphael Yuster

Qualitative Reachability in Stochastic BPA Games
Tomas Brazdil, Vaclav Brozek, Antonin Kucera and Jan Obdrzalek

Reverse Engineering Prefix Tables
Julien Cl?ment, Maxime Crochemore and Giuseppina Rindone

Computing Graph Roots of Small Girth
Babak Farzad, Lap Chi Lau, V.B. Le and Ngoc Tuy Nguyen

A Polynomial Kernel for Multicut In Trees
Nicolas Bousquet, Jean Daligault, Stephan Thomasse and Anders Yeo

Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time
Fabian Kuhn

Enumerating Homomorphisms
Andrei Bulatov, Victor Dalmau, Martin Grohe and Daniel Marx

Forward Analysis for WSTS, Part I: Completions
Alain Finkel and Jean Goubault-Larrecq

An Order on Sets of Tilings Corresponding to an Order on Languages
Nathalie Aubrun and Mathieu Sablik

Shortest Paths Avoiding Forbidden Subpaths
Mustaq Ahmed and Anna Lubiw

Kernel(s) for Problems With no Kernel: On Out-Trees With Many Leaves
Henning Fernau, Fedor Fomin, Daniel Lokshtanov, Daniel Raible, Saket Saurabh and Yngve Villanger

On Local Symmetries and Universality in Cellular Automata
Laurent Boyer and Guillaume Theyssier

Random Fruits on the Zielonka Tree
Florian Horn

Weak MSO with the unbounding quantifier
Mikolaj Bojanczyk

On the Average Complexity of Moore's State Minimization Algorithm
Fr?d?rique Bassino, Julien David and Cyril Nicaud

Deciding Unambiguity and Sequentiality of Polynomially Ambiguous min-plus Automata
Daniel Kirsten and Sylvain Lombardy

Polynomial-Time Approximation Schemes fo Subset-Connectivity Problems in Bounded-Genus Graphs
Siamak Tazari, Glencora Borradaile and Erik D. Demaine