LFCS seminar: Karoliina Lehtinen: A modal mu perspective on solving parity games in quasipolynomial time
What 


When 
Jan 30, 2018 from 04:00 PM to 05:00 PM 
Where  IF 4.31/4.33 
Add event to calendar 
vCal iCal 
Parity games are infiniteduration games on finite graph, which arise at the intersection of logic, games and automata theory. The complexity of solving parity games  i.e., deciding which player has a winning strategy  is a long standing open problem. It is known to be quasipolynomial in general, and polynomial for various restricted classes of parity games.
In this talk I present a modal mu account of the quasipolynomial solvability of parity games, based on a new quasipolynomial algorithm.
We will play a parameterised variation of parity games, called a kregister game, in which Player 0 has to produce a witness of her victory using a restricted amount of memory which depends on k. For every parity game there is a k such that solving the kregister game is equivalent to solving the parity game. We call this the registerindex of a parity game and show that it is O(log n) in the size of the parity game.
This yields a quasipolynomial algorithm for solving parity games, and a polynomial algorithm for solving games of bounded registerindex. Showing that the descriptive complexity of parity games of registerindex k depends on k, rather than on the number of priorities in the games then relates the quasipolynomial solvability of parity games to complexity in the modal mu calculus.