Deciding Parity Games in Quasipolynomial Time

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

March 1, 2017, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

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}).

---