YoVDO

Understanding and Extending the Quasipolynomial Time Algorithms for Parity Games

Offered By: Hausdorff Center for Mathematics via YouTube

Tags

Algorithm Design Courses Game Theory Courses Computational Complexity Courses

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 Processing
Columbia 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