Parity games are almost in P Event as iCalendar

(Science Event Tags, Seminars, Computer Science)

14 June 2017

1 - 2pm

Venue: 303s.561

Speaker: Bakh Khoussainov


Parity games form a class of perfect information two player games. These games emerged as an important class through their connections to model checking, verification, mu-calculus, various logics, automata theory, and Markov chains.  Given a parity game with n nodes and d colours the problem  consists of finding the winner of the game. Emerson, Jutla, and Sistla showed that the problem  is in NP and co-NP. It is an old open problem  if the winners  of parity games can be found in polynomial time.

In this talk, we define parity games, present some motivation, give examples, and explain basic ideas of the new quasi-polynomial algorithm that solves the parity games problem. As a corollary we explain why these games are fixed parameter tractable, where the parameter is d the number of colours. The algorithm significantly improves all the previously known algorithms in terms of running time.

Although the original problem is still open, this work gives a glimpse of hope towards its positive solution. 

The talk is based on the paper written jointly with C. Calude, S. Jain, W.Li, and F. Stephan. The paper received best paper award at STOC 2017 (Symposium on Theory of Computation) to be held in Montreal.