Pith. sign in

REVIEW 3 cited by

A short proof of correctness of the quasi-polynomial time algorithm for parity games

Not yet reviewed by Pith; the record is open.

Re-run · record.json Download PDF Read on arXiv ↗

This paper has not been read by Pith yet. Machine review is queued; the pith claim, tier, and objections will appear here once it completes.

SPECIMEN: schema-true, not a live event

T0 review · schema-true

One-sentence machine reading of the paper's core claim.

pith:XXXXXXXX · record.json · timestamp

arxiv 1702.01953 v4 pith:ITZUUIN3 submitted 2017-02-07 cs.FL cs.GT

Hugo Gimbert (LaBRI) , Rasmus Ibsen-Jensen (IST Austria) This is my paper · ORCID
classification cs.FLcs.GT
keywords algorithmcorrectnessgamesparityproofquasi-polynomialshorttime
verification ladder T0 review T1 audit T2 compute T3 formal
0 comments
read the original abstract

Recently Cristian S. Calude, Sanjay Jain, Bakhadyr Khoussainov, Wei Li and Frank Stephan proposed a quasi-polynomial time algorithm for parity games. This paper proposes a short proof of correctness of their algorithm.

Discussion (0). Continue with ORCID to comment.

Forward citations

Cited by 3 Pith papers

Reviewed papers in the Pith corpus that reference this work. Sorted by Pith novelty score. Full citation record

  1. Algorithms for Equilibria in Concurrent Stopping Games

    cs.GT 2026-07 accept novelty 7.0 of 10

    Approximate constrained NE existence in concurrent stopping games is EXPTIME (PSPACE-hard); XRSE constrained existence is NP-complete.

  2. Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs

    cs.DS 2026-07 accept novelty 6.0 of 10

    The Random-Action-Removal algorithm solves n-state, m-action 2-player games in e^{O(√(n ln(m/n)))} time, improving the previous e^{O(√(n ln(m/√n)))} bound by exploiting the hypercube structure of the game.

  3. Equilibria in Multiplayer Graph Games: An Algorithmic Study

    cs.GT 2026-05 unverdicted novelty 5.0 of 10

    Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.

Pith tools