Understanding and Extending the Quasipolynomial Time Algorithms for Parity Games
Offered By: Hausdorff Center for Mathematics via YouTube
Course Description
Overview
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.
Syllabus
Introduction
Overview
Positional Determinancy
Parity Games
Complexity of parity games
Universal truth
Universal trees
Fundamental theorem
Example
Other methods
Universal graphs
Graph morphism
Asymmetric algorithms
Taught by
Hausdorff Center for Mathematics
Related Courses
Natural Language ProcessingColumbia University via Coursera Intro to Algorithms
Udacity Conception et mise en œuvre d'algorithmes.
École Polytechnique via Coursera Paradigms of Computer Programming
Université catholique de Louvain via edX Data Structures and Algorithm Design Part I | 数据结构与算法设计(上)
Tsinghua University via edX