Invitation to the Logic Seminar at the National University of Singapore

Date: Wednesday, 26 October 2016, 17:00 hrs

Room: S17#04-05, Department of Mathematics, NUS

Speaker: Sanjay Jain

Title: Deciding parity games in quasipolynomial time

URL: http://www.comp.nus.edu.sg/~fstephan/logicseminar.html

Parity games are games on finite graphs where each

node has a value. Two players, Anke and Boris,

move alternately a marker through the graph

and plays between the two players have infinite

duration. One determines the winner of such an infinite

play by taking the largest value of a node which is visited

infinite often; if this value is even then the first player

Anke wins else the second player Boris wins.

An important question is to determine the player who

has a winning strategy in such games. One evaluates such

algorithms in terms of the number n of nodes and number

m of colours and other possible parameters. Prior work

has given algorithms with runtime O(n^{m/3}) and

O(n^{Sqrt(n)}). The talk will present an improved

quasipolynomial algorithm with runtime O(n^{log(m)+8}).

Furthermore, if m < log(n), one can determine the winner

in time O(n^5); thus the problem is fixed-parameter

tractable, bringing it from the prior known complexity

class XP into FPT.

This is joint work with Cristian Calude, Bakhadyr

Khoussainov, Li Wei and Frank Stephan. The paper

is available at

http://www.comp.nus.edu.sg/~sanjay/paritygame.pdf