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, Maximal Constraint Languages, and Symmetric Polymorphisms.- Regular Tree Languages Definable in FO.- Recursive Markov Chains, Stochastic Grammars, and Monotone Systems of Nonlinear Equations.- Session 5B.-