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

Prelegent(ci)

Paweł Parys

Afiliacja

Uniwersytet Warszawski

Termin

23 października 2019 14:15

Pokój

p. 5050

Seminarium

Seminarium „Teoria automatów”

---

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. 

---