IWOCA 2018: 29th International Workshop on Combinational Algorithms National University of Singapore Singapore, July 16-19, 2018 |

Department of Computer Science, National University of Singapore

13 Computing Drive, COM1, Singapore 117417, Republic of Singapore

{sanjay}@comp.nus.edu.sg

**Abstract**

In this talk we will describe a Quasi Polynomial time algorithm for parity games given by Calude et al (STOC 2017). The runtime for the algorithm is

*O*(*n*^{log(m)+6}), where *n* is the number of nodes and *m* is the number of colours (priorities). The parameterised parity game - with n nodes and m distinct colours is proven to be in the class of fixed parameter tractable problems (FPT) when parameterised over m. The corresponding runtime is *O*(*n*^{5} + *g*(*m*)), where *g*(*m*) can be taken to be *m*^{m+6}. We will also discuss the next developments in the field which improved the above algorithm by making it simultaneously in near linear space by Jurdzinski and Lazic (LICS 2017) and Fearnley et al (SPIN 2017). Recently, Lehtinen (LICS 2018) introduced the notion of register index complexity and showed that this is logarithmic in the number of nodes; furthermore, a game with register index complexity *k*, the parity game can be solved in time *m*^{O(k) . } *n*^{O(1)} which provides another quasipolynomial time algorithm for parity games.

**Bio**

Sanjay Jain did his B. Tech from IIT, Kharagpur in 1986 and his PhD in 1990 from University of Rochester. He was in University of Delaware as Assistant Professor from 1990-1992 and Institute of Systems Sciences from 1992--1994 before joining DISCS/School of Computing in 1994 where he is current working.

***** S. Jain was supported in part by the Singapore Ministry of Education Academic Research Fund Tier 2 grant MOE2016-
T2-1-019 / R146-000-234-112 and NUS grant C252-000-087-001

Department of Mathematical Informatics, Graduate School of Information Science and

Technology, The University of Tokyo

sada@mist.i.u-tokyo.ac.jp

**Abstract**

Consider **Range Minimum Query, RMQ.
** Given an array of length

In this talk, we explain an O(

**Bio**

Kunihiko SADAKANE received Ph.D. degree from The University of Tokyo in 2000. He was a research associate at Tohoku University from 2000, an associate professor at Kyushu University from 2003, an associate professor at National Institute of Informatics from 2009.

Since 2014, he has been a professor at Graduate School of Information Science and Technology, The University of Tokyo.

His research interest includes information retrieval, data structures, and data compression.

Department of Informatics, University of Bergen, Norway

E-mail: Michael.Fellows@uib.no

**Abstract**

The talk will try to do three things:

(1) Give a basic introduction to the key ideas of parameterized complexity / multivariate algorithmics, for those who may be unfamiliar with this area of research. The account will be somewhat idiosyncratic, colorful and concrete, and may offer some new perspectives even to those who are conversant in the technical ideas of this area.

(2) Briefly survey some of the key achievements of this area of research so far, and the major themes, such as the equivalency between Ptime kernelization and FPT that have emerged.

(3) Exposit recent research directions in this area that have attracted substantial new research funding in various countries of the world.

**Bio**

Mike Fellows has his PhD from the University of California, San Diego 1985. He is the Elite Professor of Computer Science at the University of Bergen, Norway.

He has in 2018 received a Norwegian Research Council Toppforsk Award of of about NOK 25 million for his project, *Parameterized Complexity for Practical Computing*. The funding scheme supports “scientific quality at the forefront of international research; boldness in scientific thinking and innovation”.

He is Associate Editor of the *Journal of Computer and System Sciences *and Associate Editor of the *ACM Transactions on Algorithms.* Fellows has over 200 published journal papers.