Sanjay Jain: Deciding parity games in quasipolynomial time

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

Leave a Reply

Your email address will not be published. Required fields are marked *

Time limit is exhausted. Please reload CAPTCHA.