Deciding Parity Games in Quasipolynomial Time

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

1 marca 2017 14:15

Pokój

p. 5870

Seminarium

Seminarium „Teoria automatów”

---

It is a long-standing open problem whether parity games can be solved in polynomial time. I will present a recent paper by Calude, Jain, Khoussainov, Li, Stephan. They have shown an algorithm that solves a parity game with n nodes and d priorities in time O(n^{log(d)+6}). The same approach gives an FPT algorithm with working time O(n^5)+f(d). This is much better than previously known algorithms, working in time n^{O(sqrt(n))} or O(n^{d/3}).

---