STACS 2005: 22nd Annual Symposium on Theoretical Aspects of Computer Science, Stuttgart, Germany, February 24-26, 2005. Proceedings

Front Matter....Pages -
Automorphisms of Finite Rings and Applications to Complexity of Problems....Pages 1-17
Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages....Pages 18-35
Algorithmics in Exponential Time....Pages 36-43
Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics....Pages 44-56
Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms....Pages 57-68
Truthful Approximation Mechanisms for Scheduling Selfish Related Machines....Pages 69-82
Counting in the Two Variable Guarded Logic with Transitivity....Pages 83-96
The Variable Hierarchy of the μ -Calculus Is Strict....Pages 97-109
The Core of a Countably Categorical Structure....Pages 110-120
How Common Can Be Universality for Cellular Automata?....Pages 121-132
Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods....Pages 133-144
On the Decidability of Temporal Properties of Probabilistic Pushdown Automata....Pages 145-157
Deciding Properties of Contract-Signing Protocols....Pages 158-169
Polylog-Time Reductions Decrease Dot-Depth....Pages 170-181
On the Computational Complexity of the Forcing Chromatic Number....Pages 182-193
More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP....Pages 194-205
Three Optimal Algorithms for Balls of Three Colors....Pages 206-217
Cost Sharing and Strategyproof Mechanisms for Set Cover Games....Pages 218-230
On Weighted Balls-into-Bins Games....Pages 231-243
Computing Minimal Multi-homogeneous Bézout Numbers Is Hard....Pages 244-255
Dynamic Complexity Theory Revisited....Pages 256-268
Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size....Pages 269-280
Shortest Monotone Descent Path Problem in Polyhedral Terrain....Pages 281-292
Packet Buffering: Randomization Beats Deterministic Algorithms....Pages 293-304
Solving Medium-Density Subset Sum Problems in Expected Polynomial Time....Pages 305-314
Quantified Constraint Satisfaction, Maximal Constraint Languages, and Symmetric Polymorphisms....Pages 315-326
Regular Tree Languages Definable in FO....Pages 327-339
Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations....Pages 340-352
Connectivity for Wireless Agents Moving on a Cycle or Grid....Pages 353-364
Improved Algorithms for Dynamic Page Migration....Pages 365-376
Approximate Range Mode and Range Median Queries....Pages 377-388
Topological Automata....Pages 389-398
Minimizing NFA’s and Regular Expressions....Pages 399-411
Increasing Kolmogorov Complexity....Pages 412-421
Kolmogorov-Loveland Randomness and Stochasticity....Pages 422-433
Information Theory in Property Testing and Monotonicity Testing in Higher Dimension....Pages 434-447
On Nash Equilibria in Non-cooperative All-Optical Networks....Pages 448-459
Speed Scaling to Manage Temperature....Pages 460-471
The Complexity of Solving Linear Equations over a Finite Ring....Pages 472-484
A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields....Pages 485-495
Characterizing TC 0 in Terms of Infinite Groups....Pages 496-507
Fast Pruning of Geometric Spanners....Pages 508-520
The PIGs Full Monty – A Floor Show of Minimal Separators....Pages 521-532
Centrality Measures Based on Current Flow....Pages 533-544
Varieties of Codes and Kraft Inequality....Pages 545-556
Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes....Pages 557-568
The Power of Commuting with Finite Sets of Words....Pages 569-580
Exact Quantum Algorithms for the Leader Election Problem....Pages 581-592
Robust Polynomials and Quantum Algorithms....Pages 593-604
Quantum Interactive Proofs with Competing Provers....Pages 605-616
Roundings Respecting Hard Constraints....Pages 617-628
Sorting Stably, In-Place, with O ( n log n ) Comparisons and O ( n ) Moves....Pages 629-640
Cycle Cover with Short Cycles....Pages 641-653
A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs....Pages 654-665
All-Pairs Nearly 2-Approximate Shortest-Paths in O ( n 2 polylog n ) Time....Pages 666-679
Pattern Occurrences in Multicomponent Models....Pages 680-692
Automatic Presentations for Finitely Generated Groups....Pages 693-704
Back Matter....Pages -