Universal trees and parity games

Starting from 2017, several quasi-polynomial algorithms for solving parity games were suggested. Using universal ordered trees and automata separation approach gives a very natural quasi-polynomial algorithm for solving parity games. Moreover, many other algorithms can be expressed in terms of automata separation approach. In the talk the construction of near-optimal universal trees will be presented and the basics of automata separation approach for solving parity games will be discussed.

The talk is based on the work of Czerwinski, Daviaud, Fijalkow, Jurdzinski, Lazic and Parys.

About lecturer: https://www.hse.ru/en/org/persons/14007605