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

Abstract

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 algorithm for parity games with running time polynomial in $q$. It is open whether a polynomial-state separation automaton exists. A positive answer will lead to a polynomial-time algorithm for parity games, while a negative answer will at least demonstrate impossibility to construct such an algorithm using separation approach. In this work we prove exponential lower bound for a restricted class of separation automata. Our technique combines communication complexity and Kolmogorov complexity. One of our technical contributions belongs to extremal combinatorics. Namely, we prove a new upper bound on the product of sizes of two families of sets with small pairwise intersection.

32 pages, 3 figures. Slight improvements of the exposition compared with version 2