@inproceedings{18955,
  abstract     = {We give a simple proof that assuming the Exponential Time Hypothesis (ETH), determining the winner of a Rabin game cannot be done in time 2o(k log k) · nO(1), where k is the number of pairs of vertex subsets involved in the winning condition and n is the vertex count of the game graph. While this result follows from the lower bounds provided by Calude et al [SIAM J. Comp. 2022], our reduction is considerably simpler and arguably provides more insight into the complexity of the problem. In fact, the analogous lower bounds discussed by Calude et al, for solving Muller games and multidimensional parity games, follow as simple corollaries of our approach. Our reduction also highlights the usefulness of a certain pivot problem — Permutation SAT — which may be of independent interest.},
  author       = {Casares, Antonio and Pilipczuk, Marcin and Pilipczuk, Michał and Souza, Uéverton S. and Thejaswini, K. S.},
  booktitle    = {2024 Symposium on Simplicity in Algorithms},
  isbn         = {9781611977936},
  location     = {Alexandria, VA, United States},
  pages        = {160--167},
  publisher    = {Society for Industrial and Applied Mathematics},
  title        = {{Simple and tight complexity lower bounds for solving Rabin games}},
  doi          = {10.1137/1.9781611977936.16},
  year         = {2024},
}