STACS 2006 23rd Annual Symposium on Theoretical Aspects of Computer Science, Marseille, France, February 23-25, 2006, Proceedings

The Ubiquitous Digital Tree.- Flat Holonomies on Automata Networks.- Interprocedurally Analyzing Polynomial Identities.- External String Sorting: Faster and Cache-Oblivious.- Amortized Rigidness in Dynamic Cartesian Trees.- Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes.- On Critical Exponents in Fixed Points of Binary k-Uniform Morphisms.- Equivalence of -Algebras and Cubic Forms.- Complete Codes in a Sofic Shift.- Kolmogorov Complexity with Error.- Kolmogorov Complexity and the Recursion Theorem.- Entanglement in Interactive Proof Systems with Binary Answers.- Quantum Algorithms for Matching and Network Flows.- The Number of Runs in a String: Improved Analysis of the Linear Upper Bound.- Estimating Entropy and Entropy Norm on Data Streams.- Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems.- Exact Price of Anarchy for Polynomial Congestion Games.- Oblivious Symmetric Alternation.- Combining Multiple Heuristics.- Conflict-Free Colorings of Rectangles Ranges.- Grid Vertex-Unfolding Orthogonal Polyhedra.- Theory and Application of Width Bounded Geometric Separator.- Invariants of Automatic Presentations and Semi-synchronous Transductions.- On the Accepting Power of 2-Tape Büchi Automata.- Weighted Picture Automata and Weighted Logics.- Markov Decision Processes with Multiple Objectives.- The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms.- Convergence and Approximation in Potential Games.- Fast FPT-Algorithms for Cleaning Grids.- Tradeoffs in Depth-Two Superconcentrators.- On Hypergraph and Graph Isomorphism with Bounded Color Classes.- Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences.- Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets.- Regularity Problems for Visibly Pushdown Languages.- Regular Expressions and NFAs Without ?-Transitions.- Redundancy in Complete Sets.- Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds.- Linear Advice for Randomized Logarithmic Space.- Nested Pebbles and Transitive Closure.- Definability of Languages by Generalized First-Order Formulas over (N,+).- Generalized Modal Satisfiability.- Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games.- DAG-Width and Parity Games.- Reliable Computations Based on Locally Decodable Codes.- Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements.- A Faster Algorithm for the Steiner Tree Problem.- Generating Randomized Roundings with Cardinality Constraints and Derandomizations.- Online Sorting Buffers on Line.- Optimal Node Routing.- Memoryless Facility Location in One Pass.- Energy-Efficient Algorithms for Flow Time Minimization.- Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games.- Datalog and Constraint Satisfaction with Infinite Templates.- Evaluating Monotone Circuits on Cylinders, Planes and Tori.- Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two.- Weighted Asynchronous Cellular Automata.- On the Complexity of the “Most General” Firing Squad Synchronization Problem.