I will talk about parity games. There are at least three different recent algorithms which solve them in quasipolynomial time. In this talk, I will show that the three algorithms can be seen as solutions of one automata-theoretic problem. Using this framework, I will show tight upper and lower bounds, witnessing a quasipolynomial barrier.

This is based on two joint works, the first with Wojtek Czerwinski, Laure Daviaud, Marcin Jurdzinski, Ranko Lazic, and Pawel Parys, and the second with Thomas Colcombet.