STACS 2005

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.