Simple and tight complexity lower bounds for solving Rabin games

Antonio Casares, Marcin Pilipczuk, Michał Pilipczuk +2

We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time $2^{o(k\log k)}\cdot n^{O(1)}$, where $k…