Proceedings / STACS 2005

Meer over het boek

The content covers a range of topics in computer science and mathematics, focusing on algorithmic complexity, combinatorics, and automata theory. It includes invited talks on automorphisms of finite rings, algebraic generating functions, and algorithmics in exponential time. The sessions delve into worst-case and average-case approximations, sampling problems, and scheduling mechanisms. Further discussions explore counting in guarded logic, the variable hierarchy of the ?-calculus, and the universality of cellular automata. Decidability of temporal properties in probabilistic automata and contract-signing protocols are also examined. The complexity of various problems, including polylog-time reductions and optimal algorithms for colored balls, is addressed, alongside cost-sharing mechanisms in set cover games. Additional topics include dynamic complexity theory, minimal Bézout numbers, and the shortest monotone descent path problem. The sessions also cover quantified constraint satisfaction, connectivity for wireless agents, and topological automata. Information theory in property testing and the complexity of solving linear equations over finite rings are highlighted, along with advancements in quantum algorithms and sorting techniques. The content concludes with discussions on minimum cycle bases in directed graphs and automatic presentations for finitely generated groups, showcasing a comprehensive exploration of contem