STACS 2007

Invited Talks.- A Calculus and Algebra for Distributed Data Management.- The Büchi Complementation Saga.- Speed-Up Techniques for Shortest-Path Computations.- Session 1A.- Compact Forbidden-Set Routing.- A New Bound for Pure Greedy Hot Potato Routing.- Wavelength Management in WDM Rings to Maximize the Number of Connections.- Session 1B.- A First Investigation of Sturmian Trees.- On the Size of the Universal Automaton of a Regular Language.- Correlations of Partial Words.- Session 2A.- Testing Convexity Properties of Tree Colorings.- Why Almost All k-Colorable Graphs Are Easy.- Session 2B.- On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds.- A New Rank Technique for Formula Size Lower Bounds.- Session 3A.- Hard Metrics from Cayley Graphs of Abelian Groups.- Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs.- Light Orthogonal Networks with Constant Geometric Dilation.- Session 3B.- Admissibility in Infinite Games.- Pure Stationary Optimal Strategies in Markov Decision Processes.- Symmetries and the Complexity of Pure Nash Equilibrium.- Session 4A.- Computing Representations of Matroids of Bounded Branch-Width.- Characterizing Minimal Interval Completions.- Session 4B.- The Complexity of Unions of Disjoint Sets.- Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity.- Session 5A.- Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets.- On the Complexity of Affine Image Matching.- Session 5B.- On Fixed Point Equations over Commutative Semirings.- An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings.- Session 6A.- A Cubic Kernel for Feedback Vertex Set.- The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting.- An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs.- Session 6B.- A Search Algorithm for the Maximal Attractor of a Cellular Automaton.- Universal Tilings.- On the Complexity of Unary