Welcome ~ Important dates ~ Invited speakers ~ Program committee ~ Previous STACS ~ Call for papers ~ Submission ~ Accepted papers ~ Registration ~ Program ~ Organizing committee ~ Accomodations ~ Travel information ~ Sponsors ~ Contact
Program
Thursday February 23, 2006
| 09:00 | Opening and Plenary Session: Invited Talk The Ubiquitous Digital Tree Chair: Bruno Durand | |
| 10:10 | Coffee break | |
| 10:40 | Session 1A Chair: Peter Sanders | Session 1B Chair: Jean-Eric Pin |
| External String Sorting: Faster and Cache-Oblivious. | On Critical Exponents in Fixed Points of Binary $k$-Uniform Morphisms. | |
| Amortized Rigidness in Dynamic Cartesian Trees. | Equivalence of F-algebras and cubic forms. | |
| Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes. | Complete codes in a sofic shift. | |
| 12:05 | Session 2A Chair: Alexander Shen | Session 2B Chair: Christoph Durr |
| Kolmogorov complexity with error. | Entanglement in Interactive Proof Systems with Binary Answers. | |
| Kolmogorov complexity and the recursion theorem. | Quantum Algorithms for Matching and Network Flows. | |
| 13:00 | Lunch | |
| 14:30 | Session 3A Chair: Christoph Durr | Session 3B Chair: Markus Lohrey |
| The Number of Runs in a String: Improved Analysis of of the Linear Upper Bound. | Exact Price of Anarchy for Polynomial Congestion Games. | |
| Estimating Entropy and Entropy Norm on Data Streams. | Oblivious Symmetric Alternation. | |
| Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems. | Combining Multiple Heuristics. | |
| 15:45 | Coffee break | |
| 16:15 | Session 4A Chair: Alexander Zvonkin | Session 4B Chair: Wolfgang Thomas |
| Conflict-Free Colorings of Rectangle Ranges. | Invariants of automatic presentations and semi-synchronous transductions. | |
| Grid Vertex-Unfolding Orthogonal Polyhedra. | On the Accepting Power of $2$-Tape B\"uchi Automata. | |
| Theory and Application of Width Bounded Geometric Separator. | Weighted Picture Automata and Weighted Logics. | |
Friday February 24, 2006
| 09:00 |
Plenary Session: Invited Talk
Symmetry Breaking in Computing Media Updated version of the paper: arXiv:cs.DC/0512077 (version 2, 22 Feb 2006) (Gene Itkis, Leonid Levin. Flat Holonomies on Automata Networks) Chair: Alexander Shen | |
| 10:00 | Coffee break | |
| 10:30 | Session 5A Chair: Miklos Santha | Session 5B Chair: Pierre Fraignaud |
| Markov Decision Processes with Multiple Objectives. | Fast FPT-algorithms for cleaning grids. | |
| The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms. | Tradeoffs in depth-two superconcentrators. | |
| Convergence and Approximation in Potential Games. | On Hypergraph and Graph Isomorphism with Bounded Color Classes. | |
| 11:55 | Session 6A Chair: Alexander Zvonkin | Session 6B Chair: Jean-Eric Pin |
| Forbidden substrings, Kolmogorov complexity and almost periodic sequences. | Regularity Problems for Visibly Pushdown Languages. | |
| Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets. | Regular expressions and NFAs without epsilon-transitions. | |
| 12:50 | Lunch | |
| 14:30 | Session 7A Chair: Jacobo Toran | Session 7B Chair: Luc Segoufin |
| Redundancy in Complete Sets. | Nested Pebbles and Transitive Closure. | |
| Sparse selfreducible sets and polynomial size circuit lower bounds. | Definability of Languages by Generalized First-Order Formulas over (N,+). | |
| Linear Advice for Randomized Logarithmic Space. | Generalized Modal Satisfiability. | |
| 15:45 | Coffee break | |
| 16:15 | Session 8A Chair: Pascal Weil | Session 8B Chair: Jacobo Toran |
| Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games. | Convergence of Autonomous Mobile Robots With Inaccurate Sensors and Movements. | |
| DAG-Width and Parity Games. | A Faster Algorithm for the Steiner Tree Problem. | |
| Reliable Computations Based on Locally Decodable Codes. | Generating Randomized Roundings with Cardinality Constraints and Derandomizations. | |
| Conference Dinner | ||
Saturday February 25, 2006
| 09:00 | Plenary Session: Invited TalkInterprocedurally Analyzing Polynomial Identities Chair: Wolfgang Thomas | |
| 10:00 | Coffee break | |
| 10:30 | Session 9A Chair: Peter Sanders | Session 9B Chair: Markus Lohrey |
| Online Sorting Buffers on Line. | Energy-Efficient Algorithms for Flow Time Minimization. | |
| Optimal Node Routing. | Efficient Analysis of Classes of Recursive Markov Decision Processes and Stochastic Games. | |
| Memoryless Facility Location in One Pass. | Datalog and Constraint Satisfaction with Infinite Templates. | |
| 11:55 | Session 10A Chair: Jacobo Toran | Session 10B Chair: Paul Gastin |
| Evaluating Monotone Circuits on Cylinders, Planes and Torii. | Weighted asynchronous cellular automata. | |
| Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two. | On the Complexity of the "Most General" Firing Squad Synchronization Problem. | |
| 12:50 | Lunch | |
STACS