  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.
