Recent Advances in Solving Parity Games

John Fearnley
University of Liverpool
Friday, 19 May, 2017 - 10:15
Salle P.OF2072

Parity games are two-player zero-sum games played on a finite graph. The problem of determining the winner of a parity games is by now a notorious open question: is there an algorithm that does this in polynomial time? Very recently, a major advance has been made towards resolving this problem. A recent paper of Calude, Jain, Khoussainov, Li, and Stephan has provided a quasi-polynomial algorithm (n^log n) for this problem. In this talk I will introduce the parity game problem, give an exposition of the new quasi-polynomial algorithm, and discuss the work by myself and others that has been inspired by this new result.