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.
A short proof of correctness of the quasi-polynomial time algorithm for parity games
2 Pith papers cite this work. Polarity classification is still indexing.
2
Pith papers citing it
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.
years
2026 2representative citing papers
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.
citing papers explorer
-
Improved subexponential analysis of the Random-Action-Removal algorithm for 2-player turn-based games and non-binary AUSOs
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.
-
Equilibria in Multiplayer Graph Games: An Algorithmic Study
Provides complexity results for the constrained existence problem of five equilibrium notions in multiplayer graph games.