Portal - STACS 2009

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

de Castelberg, Sebastian

Goubault-Larrecq, Jean

Hajiaghayi, MohammadTaghi

Marchetti-Spaccamela, Alberto

Thilikos, Dimitrios M.

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 | Privacy Published by LZI