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
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(nlog(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(n5 + g(m)), where g(m) can be taken to be mm+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 mO(k) . nO(1) which provides another quasipolynomial time algorithm for parity games.
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
Consider Range Minimum Query, RMQ.
Given an array of length n, we first construct a data structure, then given a query range, we solve the problem using the data structure. There exists a linear space (O(n) words) data structure for the RMQ problem supporting constant time queries. It is however complicated and there have been no efficient implementations until recently. In 2000, a simple solution was given and after that, constant query time RMQ data structures are used in many algorithms.
In this talk, we explain an O(n) word data structure for the RMQ problem. Then we reduce the size of the data structure to just 2n + o(n) bits. We also explain applications of the problem such as compressed suffix trees.
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
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.
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.