EATCS-IPEC Nerode Prize 2021The EATCS-IPEC Nerode Award Committee has selected the following paper as the recipient of the EATCS-IPEC Nerode Prize 2021:
A parity game is played on an $n$-vertex directed graph $G = (V, E)$ with a function $f : V \mapsto \{1, \ldots, m\}$ of colors given to the vertices. Then two players $0$ and $1$ play a game, with $0$ moving first starting from a designated start node. The players alternate, moving from the current node to one of its neighbors. This defines a possibly infinite walk on the graph. Player $0$ wins if the largest color visited infinitely often is even, and player $1$ wins otherwise. The computational complexity of the Parity Games problem of determining a winning strategy for the players for a given game with parameters $n$ and $m$ is a longstanding open problem in algorithmic game theory. The problem is important in many applications. Games played on finite graphs are deeply connected to $\mu$-calculus, various models of automata, computer aided verification, and the decidability of theories in various logics, the latter connection going back to B\"uchi. The Parity Games problem is known to be in NP and co-NP and in UP and co-UP. Prior to this paper, the fastest algorithm for Parity Games (Jurdzinsky et. al. STACS 2000) ran in $O(n^{\sqrt n})$ time. The Nerode prize winning paper provided a {\em quasi-polynomial} running time of $O(n^{6+\log(m)})$, an impressive achievement. The paper also gave an FPT algorithm with respect to parameter $m$, with running time $O(n^5+2^{6m+m\log(n)})$; the previous best dependence on $m$ was $n^{\Theta(m)}$. The deep techniques in this paper inspired a long series of further improvements on the complexity of Parity Games and related problems. The paper is a true gem in multivariate algorithmic game theory. |
