STACS 2009 February 26-28, 2009, Freiburg, Germany

26th International Symposium on Theoretical Aspects of Computer Science



Susanne Albers and Jean-Yves Marion (Eds.)
ISBN 978-3-939897-09-5, LIPICS Vol. 3 ISSN 1868-8969
Additional Information
License
Conference Website
Complete volume (PDF, 5 MB)
Search Publication Server


Authors
  • Ahmed, Mustaq
  • Albers, Susanne
  • Alwen, Joel
  • Arvind, Vikraman
  • Aubrun, Nathalie
  • Barbay, Jeremy
  • Bassino, Frederique
  • Baykan, Eda
  • Bhattacharyya, Arnab
  • Bienvenu, Laurent
  • Bojanczyk, Mikolaj
  • Borradaile, Glencora
  • Bousquet, Nicolas
  • Boyer, Laurent
  • Brazdil, Tomas
  • Briet, Jop
  • Brozek, Vaclav
  • Bulatov, Andrei A.
  • Chakraborty, Sourav
  • Chan, Ho-Leung
  • Chen, Victor
  • Chepoi, Victor
  • Cheraghchi, Mahdi
  • Clement, Julien
  • Crochemore, Maxime
  • Daligault, Jean
  • Dalmau, Victor
  • David, Julien
  • de Castelberg, Sebastian
  • Demaine, Erik D.
  • de Wolf, Ronald
  • Diekert, Volker
  • Di Lena, Pietro
  • Downey, Rod
  • Ebenlendr, Tomas
  • Edmonds, Jeff
  • Elbassioni, Khaled
  • Elsässer, Robert
  • Englert, Matthias
  • Farzad, Babak
  • Fellows, Michael R.
  • Fernau, Henning
  • Finkel, Alain
  • Fischer, Eldar
  • Fomin, Fedor V.
  • Franceschini, Gianni
  • Gacs, Peter
  • Gelade, Wouter
  • Goldberg, Leslie Ann
  • Golovach, Petr A.
  • Goubault-Larrecq, Jean
  • Grohe, Martin
  • Gronemeier, Andre
  • Grossi, Roberto
  • Guo, Jiong
  • Hajiaghayi, MohammadTaghi
  • Henzinger, Monika
  • Hermelin, Danny
  • Horn, Florian
  • Hoyrup, Mathieu
  • Hromkovic, Juraj
  • Hummel, Szczepan
  • Jerrum, Mark
  • Jez, Artur
  • Keller, Stefan F.
  • Kinzler, Markus
  • Kirsten, Daniel
  • Kratsch, Stefan
  • Krohn, Erik
  • Kucera, Antonin
  • Kufleitner, Manfred
  • Kuhn, Fabian
  • Lam, Tak-Wah
  • Landau, Gad M.
  • Landau, Shir
  • Lau, Lap Chi
  • Le, Van Bang
  • Lee, Lap-Kei
  • Le Gall, Francois
  • Lokshtanov, Daniel
  • Lombardy, Sylvain
  • Lubiw, Anna
  • Mahini, Hamid
  • Manthey, Bodo
  • Marchetti-Spaccamela, Alberto
  • Margara, Luciano
  • Marion, Jean-Yves
  • Marquardt, Marcel
  • Marx, Daniel
  • Matijevic, Domagoj
  • Matsliah, Arie
  • Mestre, Julian
  • Michalewski, Henryk
  • Moser, Hannes
  • Mukhopadhyay, Partha
  • Muthukrishnan, S.
  • Navarro, Gonzalo
  • Nicaud, Cyril
  • Niedermeier, Rolf
  • Niwinski, Damian
  • Obdrzalek, Jan
  • Okhotin, Alexander
  • Orlandi, Alessio
  • Pattinson, Dirk
  • Peikert, Chris
  • Pin, Jean-Eric
  • Pruhs, Kirk
  • Röglin, Heiko
  • Raible, Daniel
  • Raman, Rajeev
  • Rao, S. Srinivasa
  • Rindone, Giuseppina
  • Rojas, Cristobal
  • Sablik, Mathieu
  • Sauerwald, Thomas
  • Saurabh, Saket
  • Schewe, Sven
  • Schnitger, Georg
  • Schröder, Lutz
  • Schweikardt, Nicole
  • Schwentick, Thomas
  • Seston, Morgan
  • Severdija, Domagoj
  • Sgall, Jiri
  • Shokrollahi, Amin
  • Spönemann, Jacob
  • Sudan, Madhu
  • Tazari, Siamak
  • Theyssier, Guillaume
  • Thilikos, Dimitrios M.
  • Thomasse, Stephan
  • Thurley, Marc
  • Tuy, Nguyen Ngoc
  • Ueno, Kenya
  • Vöcking, Berthold
  • Villanger, Yngve
  • Weimann, Oren
  • Xie, Ning
  • Yeo, Anders
  • Yuster, Raphael
  • Zadimoghaddam, Morteza
  • Zimand, Marius

  •   
    Preface -- 26th International Symposium on Theoretical Aspects of Computer Science
    Authors: Albers, Susanne ; Marion, Jean-Yves

    Abstract | Document (96 KB) | BibTeX

    A Comparison of Techniques for Sampling Web Pages
    Authors: Baykan, Eda ; Henzinger, Monika ; Keller, Stefan F. ; de Castelberg, Sebastian ; Kinzler, Markus

    Abstract | Document (246 KB) | BibTeX

    Profinite Methods in Automata Theory
    Authors: Pin, Jean-Eric

    Abstract | Document (246 KB) | BibTeX

    Lower Bounds for Multi-Pass Processing of Multiple Data Streams
    Authors: Schweikardt, Nicole

    Abstract | Document (107 KB) | BibTeX

    Shortest Paths Avoiding Forbidden Subpaths
    Authors: Ahmed, Mustaq ; Lubiw, Anna

    Abstract | Document (206 KB) | BibTeX

    Generating Shorter Bases for Hard Random Lattices
    Authors: Alwen, Joel ; Peikert, Chris

    Abstract | Document (180 KB) | BibTeX

    Quantum Query Complexity of Multilinear Identity Testing
    Authors: Arvind, Vikraman ; Mukhopadhyay, Partha

    Abstract | Document (151 KB) | BibTeX

    An Order on Sets of Tilings Corresponding to an Order on Languages
    Authors: Aubrun, Nathalie ; Sablik, Mathieu

    Abstract | Document (195 KB) | BibTeX

    Compressed Representations of Permutations, and Applications
    Authors: Barbay, Jeremy ; Navarro, Gonzalo

    Abstract | Document (191 KB) | BibTeX

    On the Average Complexity of Moore's State Minimization Algorithm
    Authors: Bassino, Frederique ; David, Julien ; Nicaud, Cyril

    Abstract | Document (200 KB) | BibTeX

    Testing Linear-Invariant Non-Linear Properties
    Authors: Bhattacharyya, Arnab ; Chen, Victor ; Sudan, Madhu ; Xie, Ning

    Abstract | Document (188 KB) | BibTeX

    Kolmogorov Complexity and Solovay Functions
    Authors: Bienvenu, Laurent ; Downey, Rod

    Abstract | Document (183 KB) | BibTeX

    Weak MSO with the Unbounding Quantifier
    Authors: Bojanczyk, Mikolaj

    Abstract | Document (169 KB) | BibTeX

    Polynomial-Time Approximation Schemes for Subset-Connectivity Problems in Bounded-Genus Graphs
    Authors: Borradaile, Glencora ; Demaine, Erik D. ; Tazari, Siamak

    Abstract | Document (234 KB) | BibTeX

    A Polynomial Kernel for Multicut in Trees
    Authors: Bousquet, Nicolas ; Daligault, Jean ; Thomasse, Stephan ; Yeo, Anders

    Abstract | Document (237 KB) | BibTeX

    On Local Symmetries and Universality in Cellular Automata
    Authors: Boyer, Laurent ; Theyssier, Guillaume

    Abstract | Document (190 KB) | BibTeX

    Qualitative Reachability in Stochastic BPA Games
    Authors: Brazdil, Tomas ; Brozek, Vaclav ; Kucera, Antonin ; Obdrzalek, Jan

    Abstract | Document (117 KB) | BibTeX

    Locally Decodable Quantum Codes
    Authors: Briet, Jop ; de Wolf, Ronald

    Abstract | Document (188 KB) | BibTeX

    Enumerating Homomorphisms
    Authors: Bulatov, Andrei A. ; Dalmau, Victor ; Grohe, Martin ; Marx, Daniel

    Abstract | Document (118 KB) | BibTeX

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

    Abstract | Document (143 KB) | BibTeX

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

    Abstract | Document (168 KB) | BibTeX

    An Approximation Algorithm for l_infinity Fitting Robinson Structures to Distances
    Authors: Chepoi, Victor ; Seston, Morgan

    Abstract | Document (230 KB) | BibTeX

    Almost-Uniform Sampling of Points on High-Dimensional Algebraic Varieties
    Authors: Cheraghchi, Mahdi ; Shokrollahi, Amin

    Abstract | Document (187 KB) | BibTeX

    Reverse Engineering Prefix Tables
    Authors: Clement, Julien ; Crochemore, Maxime ; Rindone, Giuseppina

    Abstract | Document (178 KB) | BibTeX

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

    Abstract | Document (215 KB) | BibTeX

    Error-Correcting Data Structures
    Authors: de Wolf, Ronald

    Abstract | Document (185 KB) | BibTeX

    Fragments of First-Order Logic over Infinite Words
    Authors: Diekert, Volker ; Kufleitner, Manfred

    Abstract | Document (184 KB) | BibTeX

    Undecidable Properties of Limit Set Dynamics of Cellular Automata
    Authors: Di Lena, Pietro ; Margara, Luciano

    Abstract | Document (168 KB) | BibTeX

    Semi-Online Preemptive Scheduling: One Algorithm for All Variants
    Authors: Ebenlendr, Tomas ; Sgall, Jiri

    Abstract | Document (181 KB) | BibTeX

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

    Abstract | Document (169 KB) | BibTeX

    Cover Time and Broadcast Time
    Authors: Elsässer, Robert ; Sauerwald, Thomas

    Abstract | Document (242 KB) | BibTeX

    Economical Caching
    Authors: Englert, Matthias ; Röglin, Heiko ; Spönemann, Jacob ; Vöcking, Berthold

    Abstract | Document (176 KB) | BibTeX

    Computing Graph Roots Without Short Cycles
    Authors: Farzad, Babak ; Lau, Lap Chi ; Le, Van Bang ; Tuy, Nguyen Ngoc

    Abstract | Document (181 KB) | BibTeX

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

    Abstract | Document (221 KB) | BibTeX

    Kernel(s) for Problems with No Kernel: On Out-Trees with Many Leaves
    Authors: Fernau, Henning ; Fomin, Fedor V. ; Lokshtanov, Daniel ; Raible, Daniel ; Saurabh, Saket ; Villanger, Yngve

    Abstract | Document (193 KB) | BibTeX

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

    Abstract | Document (158 KB) | BibTeX

    Approximating Acyclicity Parameters of Sparse Hypergraphs
    Authors: Fomin, Fedor V. ; Golovach, Petr A. ; Thilikos, Dimitrios M.

    Abstract | Document (189 KB) | BibTeX

    Optimal Cache-Aware Suffix Selection
    Authors: Franceschini, Gianni ; Grossi, Roberto ; Muthukrishnan, S.

    Abstract | Document (196 KB) | BibTeX

    Randomness on Computable Probability Spaces - A Dynamical Point of View
    Authors: Gacs, Peter ; Hoyrup, Mathieu ; Rojas, Cristobal

    Abstract | Document (215 KB) | BibTeX

    The Dynamic Complexity of Formal Languages
    Authors: Gelade, Wouter ; Marquardt, Marcel ; Schwentick, Thomas

    Abstract | Document (176 KB) | BibTeX

    A Complexity Dichotomy for Partition Functions with Mixed Signs
    Authors: Goldberg, Leslie Ann ; Grohe, Martin ; Jerrum, Mark ; Thurley, Marc

    Abstract | Document (195 KB) | BibTeX

    Asymptotically Optimal Lower Bounds on the NIH-Multi-Party Information Complexity of the AND-Function and Disjointness
    Authors: Gronemeier, Andre

    Abstract | Document (176 KB) | BibTeX

    More Haste, Less Waste: Lowering the Redundancy in Fully Indexable Dictionaries
    Authors: Grossi, Roberto ; Orlandi, Alessio ; Raman, Rajeev ; Rao, S. Srinivasa

    Abstract | Document (198 KB) | BibTeX

    A Unified Algorithm for Accelerating Edit-Distance Computation via Text-Compression
    Authors: Hermelin, Danny ; Landau, Gad M. ; Landau, Shir ; Weimann, Oren

    Abstract | Document (218 KB) | BibTeX

    Random Fruits on the Zielonka Tree
    Authors: Horn, Florian

    Abstract | Document (271 KB) | BibTeX

    Ambiguity and Communication
    Authors: Hromkovic, Juraj ; Schnitger, Georg

    Abstract | Document (186 KB) | BibTeX

    On the Borel Inseparability of Game Tree Languages
    Authors: Hummel, Szczepan ; Michalewski, Henryk ; Niwinski, Damian

    Abstract | Document (244 KB) | BibTeX

    Equations over Sets of Natural Numbers with Addition Only
    Authors: Jez, Artur ; Okhotin, Alexander

    Abstract | Document (193 KB) | BibTeX

    Deciding Unambiguity and Sequentiality of Polynomially Ambiguous Min-Plus Automata
    Authors: Kirsten, Daniel ; Lombardy, Sylvain

    Abstract | Document (193 KB) | BibTeX

    Polynomial Kernelizations for MIN F^+Pi_1 and MAX NP
    Authors: Kratsch, Stefan

    Abstract | Document (196 KB) | BibTeX

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

    Abstract | Document (145 KB) | BibTeX

    Efficient Isomorphism Testing for a Class of Group Extensions
    Authors: Le Gall, Francois

    Abstract | Document (197 KB) | BibTeX

    On Approximating Multi-Criteria TSP
    Authors: Manthey, Bodo

    Abstract | Document (192 KB) | BibTeX

    Tractable Structures for Constraint Satisfaction with Truth Tables
    Authors: Marx, Daniel

    Abstract | Document (191 KB) | BibTeX

    Büchi Complementation Made Tight
    Authors: Schewe, Sven

    Abstract | Document (190 KB) | BibTeX

    Strong Completeness of Coalgebraic Modal Logics
    Authors: Schröder, Lutz ; Pattinson, Dirk

    Abstract | Document (132 KB) | BibTeX

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

    Abstract | Document (186 KB) | BibTeX

    Extracting the Kolmogorov Complexity of Strings and Sequences from Sources with Limited Independence
    Authors: Zimand, Marius

    Abstract | Document (180 KB) | BibTeX

      




    DROPS-Home | Fulltext Search | Imprint Published by LZI