STACS 2009
26th International Symposium on Theoretical Aspects of Computer Science

February 26 - 28, 2009
Freiburg - Germany
Call for Papers
Important Dates
Submission (closed)
Accepted papers
Invited Speakers
Electronic Proceedings
Registration (closed)
Travel Information
Program Committee
Organizing Committee
Previous STACS

  • 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+Π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
  • 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