An application of communication complexity, Kolmogorov complexity and extremal combinatorics to parity games

Alexander Kozachinskiy, Mikhail Vyalyi

So-called separation automata are in the core of several recently invented quasi-polynomial time algorithms for parity games. An explicit $q$-state separation automaton implies an…