Universal trees grow inside separating automata: Quasi-polynomial lower bounds for parity games

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

30 maja 2018 14:15

Pokój

p. 5050

Tytuł w języku angielskim

joint work with Wojciech Czerwiński, Laure Daviaud, Nathanael Fijalkow, Marcin Jurdziński, Ranko Lazić

Seminarium

Seminarium „Teoria automatów”

---

Several distinct techniques have been proposed to design quasi-polynomial algorithms for solving parity games
since the breakthrough result of Calude, Jain, Khoussainov, Li, and Stephan (2017): play summaries, progress measures and universal trees, and register games.
We argue thatall those techniques can be viewed as instances of the separation approach to solving parity games,
a key technical component of which is constructing (explicitly or implicitly) an automaton
that separates languages of words encoding plays that are (decisively) won by either ofthe two players.
Our main technical result is a quasi-polynomial lowerbound on the size of such separating automata that nearly matches the current best upper bounds.
This forms a barrier that all existing approaches must overcome in the ongoing quest for a polynomial-time algorithm for solving parity games.
The technical highlight is a proof that every separating safety automaton has a universal tree hidden in its state space;
our lower bound then follows by establishing a quasi-polynomial lower bound for universal trees.

This is joint work with Wojciech Czerwiński, Laure Daviaud, Nathanael Fijalkow, Marcin Jurdziński, Ranko Lazić.

---