Alladi Ramakrishnan Hall

Solving parity games in quasi-polynomial time

Abhijith R Nair

IMSc

This talk will be focused on Parity Games, which is a two player game on a directed graph. These games are of interest since they have applications in model checking, verification. Despite their significance, complexity of solving parity games over finite graphs has been a long standing open problem and still continues to be open. Thus in this talk, we will be looking at an algorithm to solve parity games over finite graphs in quasi-polynomial time as opposed to the usual exponential algorithm. This algorithm will be leveraging the fact that parity games over finite graphs can be reduced to a simpler game that can be solved efficiently.