Understanding and Extending the Quasipolynomial Time Algorithms for Parity Games

Understanding and Extending the Quasipolynomial Time Algorithms for Parity Games

Explore the world of two-player parity games and their extensions in this 29-minute talk from the Hausdorff Center for Mathematics. Delve into the quasipolynomial time algorithms developed since the 2017 breakthrough, examining their connections to universal trees. Discover how universal graphs serve as a powerful tool for creating game-solving algorithms. Learn about recent developments, including partial complexity lower bounds, new algorithms for mean payoff games, and tropical interpretations of universal graphs. Gain insights into positional determinancy, the complexity of parity games, and asymmetric algorithms through examples and fundamental theorems.