---
OA_place: repository
OA_type: green
_id: '18955'
abstract:
- lang: eng
  text: 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.
acknowledgement: This work is a part of projects CUTACOMBS (Ma. Pilipczuk), BOBR (Mi.
  Pilipczuk), and VAMOS (K. S. Thejaswini) that have received funding from the European
  Research Council (ERC) under the European Union's Horizon 2020 research and innovation
  programme, grant agreements No 714704, 948057, and 101020093, respectively. Ma.
  Pilipczuk is also partially supported by Polish National Science Centre SONATA BIS-12
  grant number 2022/46/E/ST6/00143.
article_processing_charge: No
arxiv: 1
author:
- first_name: Antonio
  full_name: Casares, Antonio
  last_name: Casares
- first_name: Marcin
  full_name: Pilipczuk, Marcin
  last_name: Pilipczuk
- first_name: Michał
  full_name: Pilipczuk, Michał
  last_name: Pilipczuk
- first_name: Uéverton S.
  full_name: Souza, Uéverton S.
  last_name: Souza
- first_name: K. S.
  full_name: Thejaswini, K. S.
  id: 3807fb92-fdc1-11ee-bb4a-b4d8a431c753
  last_name: Thejaswini
citation:
  ama: 'Casares A, Pilipczuk M, Pilipczuk M, Souza US, Thejaswini KS. Simple and tight
    complexity lower bounds for solving Rabin games. In: <i>2024 Symposium on Simplicity
    in Algorithms</i>. Society for Industrial and Applied Mathematics; 2024:160-167.
    doi:<a href="https://doi.org/10.1137/1.9781611977936.16">10.1137/1.9781611977936.16</a>'
  apa: 'Casares, A., Pilipczuk, M., Pilipczuk, M., Souza, U. S., &#38; Thejaswini,
    K. S. (2024). Simple and tight complexity lower bounds for solving Rabin games.
    In <i>2024 Symposium on Simplicity in Algorithms</i> (pp. 160–167). Alexandria,
    VA, United States: Society for Industrial and Applied Mathematics. <a href="https://doi.org/10.1137/1.9781611977936.16">https://doi.org/10.1137/1.9781611977936.16</a>'
  chicago: Casares, Antonio, Marcin Pilipczuk, Michał Pilipczuk, Uéverton S. Souza,
    and K. S. Thejaswini. “Simple and Tight Complexity Lower Bounds for Solving Rabin
    Games.” In <i>2024 Symposium on Simplicity in Algorithms</i>, 160–67. Society
    for Industrial and Applied Mathematics, 2024. <a href="https://doi.org/10.1137/1.9781611977936.16">https://doi.org/10.1137/1.9781611977936.16</a>.
  ieee: A. Casares, M. Pilipczuk, M. Pilipczuk, U. S. Souza, and K. S. Thejaswini,
    “Simple and tight complexity lower bounds for solving Rabin games,” in <i>2024
    Symposium on Simplicity in Algorithms</i>, Alexandria, VA, United States, 2024,
    pp. 160–167.
  ista: 'Casares A, Pilipczuk M, Pilipczuk M, Souza US, Thejaswini KS. 2024. Simple
    and tight complexity lower bounds for solving Rabin games. 2024 Symposium on Simplicity
    in Algorithms. SOSA: Symposium on Simplicity in Algorithms, 160–167.'
  mla: Casares, Antonio, et al. “Simple and Tight Complexity Lower Bounds for Solving
    Rabin Games.” <i>2024 Symposium on Simplicity in Algorithms</i>, Society for Industrial
    and Applied Mathematics, 2024, pp. 160–67, doi:<a href="https://doi.org/10.1137/1.9781611977936.16">10.1137/1.9781611977936.16</a>.
  short: A. Casares, M. Pilipczuk, M. Pilipczuk, U.S. Souza, K.S. Thejaswini, in:,
    2024 Symposium on Simplicity in Algorithms, Society for Industrial and Applied
    Mathematics, 2024, pp. 160–167.
conference:
  end_date: 2024-01-10
  location: Alexandria, VA, United States
  name: 'SOSA: Symposium on Simplicity in Algorithms'
  start_date: 2024-01-08
date_created: 2025-01-29T11:55:50Z
date_published: 2024-01-01T00:00:00Z
date_updated: 2025-04-14T07:55:54Z
day: '01'
department:
- _id: ToHe
doi: 10.1137/1.9781611977936.16
ec_funded: 1
external_id:
  arxiv:
  - '2310.20433'
language:
- iso: eng
main_file_link:
- open_access: '1'
  url: https://doi.org/10.48550/arXiv.2310.20433
month: '01'
oa: 1
oa_version: Preprint
page: 160-167
project:
- _id: 62781420-2b32-11ec-9570-8d9b63373d4d
  call_identifier: H2020
  grant_number: '101020093'
  name: Vigilant Algorithmic Monitoring of Software
publication: 2024 Symposium on Simplicity in Algorithms
publication_identifier:
  isbn:
  - '9781611977936'
publication_status: published
publisher: Society for Industrial and Applied Mathematics
quality_controlled: '1'
scopus_import: '1'
status: public
title: Simple and tight complexity lower bounds for solving Rabin games
type: conference
user_id: 2DF688A6-F248-11E8-B48F-1D18A9856A87
year: '2024'
...