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 Briët and Ronald de Wolf
Ambiguity and Communication

Juraj Hromkovič 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

Dániel Marx
A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression

Danny Hermelin, Gad M. 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 Gács, Mathieu Hoyrup and Cristóbal 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⁺Π₁ 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
Büchi Complementation Made Tight

Sven Schewe
A Generalization of Nemhauser and Trotter's Local Optimization Theorem

Michael R. 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 Jeż and Alexander Okhotin
On the Borel Inseparability of Game Tree Languages

Szczepan Hummel, Henryk Michalewski and Damian Niwiński
Generating Shorter Bases for Hard Random Lattices

Joël Alwen and Chris Peikert
An Approximation Algorithm for l_∞-Fitting Robinson Structures to Distances

Victor Chepoi and Morgan Seston
Improved Approximations for Guarding 1.5-Dimensional Terrains

Khaled Elbassioni, Erik Krohn, Domagoj Matijević, Julián Mestre and Domagoj Ševerdija
Economical Caching

Matthias Englert, Heiko Röglin, 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 S. Srinivasa Rao
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 Jiří 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

Tomáš Brázdil, Václav Brožek, Antonín Kučera and Jan Obdržálek
Reverse Engineering Prefix Tables

Julien Clément, Maxime Crochemore and Giuseppina Rindone
Computing Graph Roots Without Short Cycles

Babak Farzad, Lap Chi Lau, Van Bang Le and Nguyen Ngoc Tuy
A Polynomial Kernel for Multicut In Trees

Nicolas Bousquet, Jean Daligault, Stéphan Thomassé and Anders Yeo
Local Multicoloring Algorithms: Computing a Nearly-Optimal TDMA Schedule in Constant Time

Fabian Kuhn
Enumerating Homomorphisms

Andrei A. Bulatov, Víctor Dalmau, Martin Grohe and Dániel 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 V. 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

Mikołaj Bojańczyk
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 for Subset-Connectivity Problems in Bounded-Genus Graphs

Glencora Borradaile, Erik D. Demaine and Siamak Tazari