STACS 2005

The Symposium on Theoretical Aspects of Computer Science (STACS) is alt- nately held in France and in Germany. The conference of February 24 26, 2005 inStuttgartwasthetwenty-secondinthisseries.Previousmeetingstookplacein Paris(1984),Saarbruc ken(1985),Orsay(1986),Passau(1987),Bordeaux(1988), Paderborn (1989), Rouen (1990), Hamburg (1991), Cachan (1992), Wurzburg (1993), Caen (1994), Munc hen (1995), Grenoble (1996), Lub eck (1997), Paris (1998), Trier (1999), Lille (2000), Dresden (2001), Antibes (2002), Berlin (2003), and Montpellier (2004). The interest in STACS has been increasing continuously during recent years and has turned it into a leading conference in theoretical computer science. The call for papers for STACS 2005 led to 217 submissions from all over the world. The 17 members of the Program Committee met in Stuttgart for two days at the end of October 2004 to select the contributions to be presented at the conference.Thanksareduetothecommitteeaswellastoalltheexternalreferees for their valuable work put into the reviewing process. Just 54 papers (i.e., 25% of the submissions) could be accepted, thus guaranteeing the very high scienti?c quality of the conference. Moreover, this strict selection enabled us to keep the conference in its standard format with only two parallel sessions. We would like to thank the three invited speakers Manindra Agrawal (Sin- pore), Mireille Bousquet-M elou (Bordeaux), and Uwe Schoning (Ulm) for p- senting lectures and for their contributions to the proceedings. Finally we thank the local organizing committee and all members of the Institute of Formal Methods in Computer Science for their help. In particular wethankHolgerAustinat,HeikePhotien,andHorstProtefortheirgreate?orts.

Inhalt
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.