Parity Games: Zielonka’s Algorithm in Quasi-Polynomial Time

Speaker(s)

Paweł Parys

Affiliation

Uniwersytet Warszawski

Date

Oct. 23, 2019, 2:15 p.m.

Room

room 5050

Seminar

Seminar Automata Theory

---

Calude, Jain, Khoussainov, Li, and Stephan (2017) proposed a quasi-polynomial-time algorithm solving parity games.

After this breakthrough result, a few other quasi-polynomial-time algorithms were introduced; none of them is easy to understand. Moreover, it turns out that in practice they operate very slowly.

On the other side there is the Zielonka’s recursive algorithm, which is very simple, exponential in the worst case, and the fastest in practice.

 

We combine these two approaches: we propose a small modification of the Zielonka’s algorithm, which ensures that the running time is at most quasi-polynomial.

In effect, we obtain a simple algorithm that solves parity games in quasi-polynomial time. 

---