A Technique to Speed up Some Symmetric Attractor-based Algorithms for Parity Games

Abstract

It is well known that the classic McNaughton-Zielonka algorithm for solving parity games has excellent performance in practice, but its worst-case asymptotic complexity is worse than that of the state-of-the-art algorithms. K.S. Thejaswini will present their work which pinpoints the mechanism that is responsible for this relative underperformance and propose a new technique that eliminates it. Their new technique is based on firstly enhancing the algorithm to compute attractor decompositions' of subgames instead of just winning strategies on them, and then on making it carefully use attractor decompositions computed in prior recursive calls. This results in a theoretical improvement in the run-time complexity of not just McNaughton and Zielonka, but these techniques also improve several other attractor-based algorithms' theoretical run-time. We also suggest different heuristics which can further potentially enhance the practical running time of these algorithms.

Bio

K.S. Thejaswini is a third year PhD student at the university of Warwick in the UK, and her supervisor is Marcin Jurdzinksi. Her PhD is broadly on solving parity games faster and in her PhD, she aims to understand several parity games algorithms better. She enjoys working on problems from the perspective of games, but more broadly, she is interested in problems in logic, automata, and games.
Find her website here.