# A Recursive Approach to Solving Parity Games in Quasipolynomial Time

arXiv: https://arxiv.org/abs/2104.09717 · HTML: https://mlsanity.com/paper/2104.09717/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 20 Apr 2021.

## Built on by (most cited first, 1 of 1)

- [Guessing Winning Policies in LTL Synthesis by Semantic Learning](https://mlsanity.com/paper/2305.15109/) (2023)

## Abstract (arXiv)

Zielonka's classic recursive algorithm for solving parity games is perhaps the simplest among the many existing parity game algorithms. However, its complexity is exponential, while currently the state-of-the-art algorithms have quasipolynomial complexity. Here, we present a modification of Zielonka's classic algorithm that brings its complexity down to n^Oleft(logleft(1+fracdlog nright)right), for parity games of size n with d priorities, in line with previous quasipolynomial-time solutions.