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

This book constitutes the refereed proceedings of the 22nd Annual Symposium on Theoretical Aspects of Computer Science, STACS 2005, held in Stuttgart, Germany in February 2005.
The 54 revised full papers presented together with 3 invited papers were carefully reviewed and selected from 217 submissions. A broad variety of topics from theoretical computer science are addressed, in particular complexity theory, algorithmics, computational discrete mathematics, automata theory, combinatorial optimization and approximation, networking and graph theory, computational geometry, grammar systems and formal languages, etc.

Invited Talks.- Automorphisms of Finite Rings and Applications to Complexity of Problems.- Algebraic Generating Functions in Enumerative Combinatorics and Context-Free Languages.- Algorithmics in Exponential Time.- Session 1A.- Worst-Case and Average-Case Approximations by Simple Randomized Search Heuristics.- Sampling Sub-problems of Heterogeneous Max-cut Problems and Approximation Algorithms.- Truthful Approximation Mechanisms for Scheduling Selfish Related Machines.- Session 1B.- Counting in the Two Variable Guarded Logic with Transitivity.- The Variable Hierarchy of the ?-Calculus Is Strict.- The Core of a Countably Categorical Structure.- Session 2A.- How Common Can Be Universality for Cellular Automata?.- Cellular Automata: Real-Time Equivalence Between One-Dimensional Neighborhoods.- Session 2B.- On the Decidability of Temporal Properties of Probabilistic Pushdown Automata.- Deciding Properties of Contract-Signing Protocols.- Session 3A.- Polylog-Time Reductions Decrease Dot-Depth.- On the Computational Complexity of the Forcing Chromatic Number.- More Efficient Queries in PCPs for NP and Improved Approximation Hardness of Maximum CSP.- Session 3B.- Three Optimal Algorithms for Balls of Three Colors.- Cost Sharing and Strategyproof Mechanisms for Set Cover Games.- On Weighted Balls-into-Bins Games.- Session 4A.- Computing Minimal Multi-homogeneous Bézout Numbers Is Hard.- Dynamic Complexity Theory Revisited.- Parametric Duality and Kernelization: Lower Bounds and Upper Bounds on Kernel Size.- Session 4B.- Shortest Monotone Descent Path Problem in Polyhedral Terrain.- Packet Buffering: Randomization Beats Deterministic Algorithms.- Solving Medium-Density Subset Sum Problems in Expected Polynomial Time.- Session 5A.- Quantified Constraint Satisfaction, MaximalConstraint Languages, and Symmetric Polymorphisms.- Regular Tree Languages Definable in FO.- Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations.- Session 5B.- Connectivity for Wireless Agents Moving on a Cycle or Grid.- Improved Algorithms for Dynamic Page Migration.- Approximate Range Mode and Range Median Queries.- Session 6A.- Topological Automata.- Minimizing NFA’s and Regular Expressions.- Session 6B.- Increasing Kolmogorov Complexity.- Kolmogorov-Loveland Randomness and Stochasticity.- Session 7A.- Information Theory in Property Testing and Monotonicity Testing in Higher Dimension.- On Nash Equilibria in Non-cooperative All-Optical Networks.- Speed Scaling to Manage Temperature.- Session 7B.- The Complexity of Solving Linear Equations over a Finite Ring.- A Lower Bound on the Complexity of Polynomial Multiplication Over Finite Fields.- Characterizing TC0 in Terms of Infinite Groups.- Session 8A.- Fast Pruning of Geometric Spanners.- The PIGs Full Monty – A Floor Show of Minimal Separators.- Centrality Measures Based on Current Flow.- Session 8B.- Varieties of Codes and Kraft Inequality.- Improving the Alphabet-Size in High Noise, Almost Optimal Rate List Decodable Codes.- The Power of Commuting with Finite Sets of Words.- Session 9A.- Exact Quantum Algorithms for the Leader Election Problem.- Robust Polynomials and Quantum Algorithms.- Quantum Interactive Proofs with Competing Provers.- Session 9B.- Roundings Respecting Hard Constraints.- Sorting Stably, In-Place, with O(n log n) Comparisons and O(n) Moves.- Cycle Cover with Short Cycles.- Session 10A.- A Polynomial Time Algorithm for Minimum Cycle Basis in Directed Graphs.- All-Pairs Nearly 2-Approximate Shortest-Paths in O(n 2 polylog n) Time.- Session 10B.- PatternOccurrences in Multicomponent Models.- Automatic Presentations for Finitely Generated Groups.