STACS 2007: 24th Annual Symposium on Theoretical Aspects of Computer Science, Aachen, Germany, February 22-24, 2007. Proceedings

Front Matter....Pages -
A Calculus and Algebra for Distributed Data Management....Pages 1-11
The Büchi Complementation Saga....Pages 12-22
Speed-Up Techniques for Shortest-Path Computations....Pages 23-36
Compact Forbidden-Set Routing....Pages 37-48
A New Bound for Pure Greedy Hot Potato Routing....Pages 49-60
Wavelength Management in WDM Rings to Maximize the Number of Connections....Pages 61-72
A First Investigation of Sturmian Trees....Pages 73-84
On the Size of the Universal Automaton of a Regular Language....Pages 85-96
Correlations of Partial Words....Pages 97-108
Testing Convexity Properties of Tree Colorings....Pages 109-120
Why Almost All k -Colorable Graphs Are Easy....Pages 121-132
On Defining Integers in the Counting Hierarchy and Proving Arithmetic Circuit Lower Bounds....Pages 133-144
A New Rank Technique for Formula Size Lower Bounds....Pages 145-156
Hard Metrics from Cayley Graphs of Abelian Groups....Pages 157-162
Broadcasting vs. Mixing and Information Dissemination on Cayley Graphs....Pages 163-174
Light Orthogonal Networks with Constant Geometric Dilation....Pages 175-187
Admissibility in Infinite Games....Pages 188-199
Pure Stationary Optimal Strategies in Markov Decision Processes....Pages 200-211
Symmetries and the Complexity of Pure Nash Equilibrium....Pages 212-223
Computing Representations of Matroids of Bounded Branch-Width....Pages 224-235
Characterizing Minimal Interval Completions....Pages 236-247
The Complexity of Unions of Disjoint Sets....Pages 248-259
Kolmogorov-Loveland Stochasticity and Kolmogorov Complexity....Pages 260-271
Bounded-Hop Energy-Efficient Broadcast in Low-Dimensional Metrics Via Coresets....Pages 272-283
On the Complexity of Affine Image Matching....Pages 284-295
On Fixed Point Equations over Commutative Semirings....Pages 296-307
An Exponential Lower Bound for Prefix Gröbner Bases in Free Monoid Rings....Pages 308-319
A Cubic Kernel for Feedback Vertex Set....Pages 320-331
The Union of Minimal Hitting Sets: Parameterized Combinatorial Bounds and Counting....Pages 332-343
An Optimal, Edges-Only Fully Dynamic Algorithm for Distance-Hereditary Graphs....Pages 344-355
A Search Algorithm for the Maximal Attractor of a Cellular Automaton....Pages 356-366
Universal Tilings....Pages 367-380
On the Complexity of Unary Tiling-Recognizable Picture Languages....Pages 381-392
A Characterization of Strong Learnability in the Statistical Query Model....Pages 393-404
On the Consistency of Discrete Bayesian Learning....Pages 405-416
VPSPACE and a Transfer Theorem over the Reals....Pages 417-428
On Symmetric Signatures in Holographic Algorithms....Pages 429-440
Randomly Rounding Rationals with Cardinality Constraints and Derandomizations....Pages 441-452
Cheating to Get Better Roommates in a Random Stable Matching....Pages 453-464
A Deterministic Algorithm for Summarizing Asynchronous Streams over a Sliding Window....Pages 465-476
Arithmetizing Classes Around NC 1 and L ....Pages 477-488
The Polynomially Bounded Perfect Matching Problem Is in NC 2 ....Pages 489-499
Languages with Bounded Multiparty Communication Complexity....Pages 500-511
New Approximation Algorithms for Minimum Cycle Bases of Graphs....Pages 512-523
On Completing Latin Squares....Pages 524-535
Small Space Representations for Metric Min-Sum k -Clustering and Their Applications....Pages 536-548
An Optimal Tableau-Based Decision Algorithm for Propositional Neighborhood Logic....Pages 549-560
Bounded-Variable Fragments of Hybrid Logics....Pages 561-572
Rank-1 Modal Logics Are Coalgebraic....Pages 573-585
An Efficient Quantum Algorithm for the Hidden Subgroup Problem in Extraspecial Groups....Pages 586-597
Weak Fourier-Schur Sampling, the Hidden Subgroup Problem, and the Quantum Collision Problem....Pages 598-609
Quantum Network Coding....Pages 610-621
Reachability in Unions of Commutative Rewriting Systems Is Decidable....Pages 622-633
Associative-Commutative Deducibility Constraints....Pages 634-645
On the Automatic Analysis of Recursive Security Protocols with XOR....Pages 646-657
Improved Online Algorithms for the Sorting Buffer Problem....Pages 658-669
Cost Sharing Methods for Makespan and Completion Time Scheduling....Pages 670-681
Planar Graphs: Logical Complexity and Parallel Isomorphism Tests....Pages 682-693
Enumerating All Solutions for Constraint Satisfaction Problems....Pages 694-705
Back Matter....Pages -