## Speaker:

## Affiliation:

## Time:

It is shown that the Strahler number of a parity game is a robust, and hence arguably natural, parameter: it coincides with its alternative version based on trees of progress measures and—remarkably—with the register number defined by Lehtinen (2018). It follows that parity games can be solved in quasi-linear space and in time that is polynomial in the number of vertices and linear in (d/2k)^k, where k is the register number. This significantly improves the running times and space achieved for parity games of bounded register number by Lehtinen (2018) and by Parys(2020). The running time of the algorithm based on small Strahler-universal trees yields a novel trade-off k.log(d/k) = O(log n) between the two natural parameters that measure the structural complexity of a parity game, which allows solving parity games in polynomial time. This includes as special cases the asymptotic settings of those parameters covered by the results of Calude, Jain, Khoussainov, Li, and Stephan (2017), of Jurdzinski and Lazic (2017), and of Lehtinen (2018), and it significantly extends the range of such settings, for example to d = 2^{O(\sqrt{\lg n})} and k = O(\sqrt{\lg n}).

This is joint work with Laure Daviaud and Marcin Jurdzinski.

Zoom link: https://zoom.us/j/93889521556?pwd=eEFJWVRtRHNpNlpZWmhNYTJGQTF6Zz09