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-OnlyFully 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 Tiling-Recognizable Picture Languages.- Session 7A.- A Characterization of Strong Learnability in the Statistical Query Model.- On the Consistency of Discrete Bayesian Learning.- Session 7B.- VPSPACE and a Transfer Theorem over the Reals.- On Symmetric Signatures in Holographic Algorithms.- Session 8A.- Randomly Rounding Rationals with Cardinality Constraints and Derandomizations.- Cheating to Get Better Roommates in a Random Stable Matching.- A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window.- Session 8B.- Arithmetizing Classes Around NC 1 and L.- The Polynomially Bounded Perfect Matching Problem Is in NC 2.- Languages with Bounded Multiparty Communication Complexity.- Session 9A.- New Approximation Algorithms for Minimum Cycle Bases of Graphs.- On Completing Latin Squares.- Small Space Representations for Metric Min-Sum k-Clustering and Their Applications.- Session 9B.- An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic.- Bounded-Variable Fragments of Hybrid Logics.- Rank-1 Modal Logics Are Coalgebraic.- Session 10A.- An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups.- Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem.- Quantum Network Coding.- Session 10B.- Reachability in Unions of Commutative Rewriting Systems Is Decidable.- Associative-Commutative Deducibility Constraints.- On the Automatic Analysis of Recursive Security Protocols with XOR.- Session 11A.- Improved Online Algorithms for the Sorting Buffer Problem.- Cost Sharing Methods forMakespan and Completion Time Scheduling.- Session 11B.- Planar Graphs: Logical Complexity and Parallel Isomorphism Tests.- Enumerating All Solutions for Constraint Satisfaction Problems.