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

Front Matter....Pages -
The Ubiquitous Digital Tree....Pages 1-22
Flat Holonomies on Automata Networks....Pages 23-49
Interprocedurally Analyzing Polynomial Identities....Pages 50-67
External String Sorting: Faster and Cache-Oblivious....Pages 68-79
Amortized Rigidness in Dynamic Cartesian Trees....Pages 80-91
Distribution-Sensitive Construction of Minimum-Redundancy Prefix Codes....Pages 92-103
On Critical Exponents in Fixed Points of Binary k -Uniform Morphisms....Pages 104-114
Equivalence of $\mathbb{F}$ -Algebras and Cubic Forms....Pages 115-126
Complete Codes in a Sofic Shift....Pages 127-136
Kolmogorov Complexity with Error....Pages 137-148
Kolmogorov Complexity and the Recursion Theorem....Pages 149-161
Entanglement in Interactive Proof Systems with Binary Answers....Pages 162-171
Quantum Algorithms for Matching and Network Flows....Pages 172-183
The Number of Runs in a String: Improved Analysis of the Linear Upper Bound....Pages 184-195
Estimating Entropy and Entropy Norm on Data Streams....Pages 196-205
Pay Today for a Rainy Day: Improved Approximation Algorithms for Demand-Robust Min-Cut and Shortest Path Problems....Pages 206-217
Exact Price of Anarchy for Polynomial Congestion Games....Pages 218-229
Oblivious Symmetric Alternation....Pages 230-241
Combining Multiple Heuristics....Pages 242-253
Conflict-Free Colorings of Rectangles Ranges....Pages 254-263
Grid Vertex-Unfolding Orthogonal Polyhedra....Pages 264-276
Theory and Application of Width Bounded Geometric Separator....Pages 277-288
Invariants of Automatic Presentations and Semi-synchronous Transductions....Pages 289-300
On the Accepting Power of 2-Tape Büchi Automata....Pages 301-312
Weighted Picture Automata and Weighted Logics....Pages 313-324
Markov Decision Processes with Multiple Objectives....Pages 325-336
The Algorithmic Structure of Group Strategyproof Budget-Balanced Cost-Sharing Mechanisms....Pages 337-348
Convergence and Approximation in Potential Games....Pages 349-360
Fast FPT-Algorithms for Cleaning Grids....Pages 361-371
Tradeoffs in Depth-Two Superconcentrators....Pages 372-383
On Hypergraph and Graph Isomorphism with Bounded Color Classes....Pages 384-395
Forbidden Substrings, Kolmogorov Complexity and Almost Periodic Sequences....Pages 396-407
Online Learning and Resource-Bounded Dimension: Winnow Yields New Lower Bounds for Hard Sets....Pages 408-419
Regularity Problems for Visibly Pushdown Languages....Pages 420-431
Regular Expressions and NFAs Without ε -Transitions....Pages 432-443
Redundancy in Complete Sets....Pages 444-454
Sparse Selfreducible Sets and Polynomial Size Circuit Lower Bounds....Pages 455-468
Linear Advice for Randomized Logarithmic Space....Pages 469-476
Nested Pebbles and Transitive Closure....Pages 477-488
Definability of Languages by Generalized First-Order Formulas over ( N ,+)....Pages 489-499
Generalized Modal Satisfiability....Pages 500-511
Strategy Improvement and Randomized Subexponential Algorithms for Stochastic Parity Games....Pages 512-523
DAG-Width and Parity Games....Pages 524-536
Reliable Computations Based on Locally Decodable Codes....Pages 537-548
Convergence of Autonomous Mobile Robots with Inaccurate Sensors and Movements....Pages 549-560
A Faster Algorithm for the Steiner Tree Problem....Pages 561-570
Generating Randomized Roundings with Cardinality Constraints and Derandomizations....Pages 571-583
Online Sorting Buffers on Line....Pages 584-595
Optimal Node Routing....Pages 596-607
Memoryless Facility Location in One Pass....Pages 608-620
Energy-Efficient Algorithms for Flow Time Minimization....Pages 621-633
Efficient Qualitative Analysis of Classes of Recursive Markov Decision Processes and Simple Stochastic Games....Pages 634-645
Datalog and Constraint Satisfaction with Infinite Templates....Pages 646-659
Evaluating Monotone Circuits on Cylinders, Planes and Tori....Pages 660-671
Constant-Depth Circuits for Arithmetic in Finite Fields of Characteristic Two....Pages 672-683
Weighted Asynchronous Cellular Automata....Pages 684-695
On the Complexity of the “Most General” Firing Squad Synchronization Problem....Pages 696-711
Back Matter....Pages -