Subexponential algorithms for solving parity games

Speaker(s)

Marcin Jurdziński

Affiliation

Uniwersytet Warszawski

Date

Nov. 23, 2006, 2:15 p.m.

Room

room 5870

Seminar

Seminar Automata Theory

---

Solving parity games is polynomial time equivalent to the modal mu-calculus model checking problem and its exact computational complexity is an intriguing open problem: it is known to be in UP (unambiguous NP) and co-UP, but no polynomial time algorithm is known. This talk surveys a few recent algorithmic ideas which yield improved running time bounds for the problem. One is obtained by a reduction of parity games to the problem of finding the unique sink in a "unique sink orientation" of a hypercube and it yields a subexponential randomized algorithm. The other is a modification of a classical recursive algorithm for solving parity games that originates from the work of McNaughton and Zielonka and it yields a subexponential deterministic algorithm.

---