21 July 2017 – Professors Sanjay Jain and Frank Stephan, and their collaborators, Wei Li from NUS’ Department of Mathematics, and Professors Cristian Calude and Bakhadyr Khoussainov from the University of Auckland, won the STOC 2017 Best Paper Award for their paper, ‘Deciding Parity Games in Quasipolynomial Time’, at STOC 2017 Theory Fest: the 49th ACM Symposium on the Theory of Computing.
The premier conference in theoretical computer science was held in Montreal, Canada, in mid-June.
Speaking on behalf of his collaborators, Prof Stephan said, “The research improved the speed of the best verified algorithm for solving all parity games. A parity game has two players, Anke and Boris. They move alternately in a directed finite graph where every node has a value and each node has at least one edge to a successor node. Furthermore, each node has a number from 1 to m and the infinite play produces an infinite sequence of numbers according to the nodes visited. Now player Anke wins if the largest infinitely often appearing number in this sequence is odd and player Boris wins if that number is even. The research question on this parity games is to find a fast algorithm which determines which player has a winning strategy.”
According to Prof Stephan, there was a roughly exponential improvement in the running time of verified algorithms (i.e. of algorithms where it is proven that in all cases they have the promised running time). Some algorithms are faster in many practical relevant instances of parity games, but they also fail to keep their promise and are exponentially slow on other instances of parity games.
“The question whether the current quasipolynomial running time can be brought down to polynomial running time is still an important question and although this paper did not solve this original question, it has contributed a big step forward towards a solution of this question,” said Prof Stephan.
The Annual ACM Symposium on Theory of Computing (STOC), is the flagship conference of SIGACT, the Special Interest Group on Algorithms and Computation Theory, a special interest group of the Association for Computing Machinery (ACM). It has been held annually since 1969, traditionally in May/June.
SIGACT is an international organization that fosters and promotes the discovery and dissemination of high quality research in theoretical computer science (TCS), the formal analysis of efficient computation and computational processes. SIGACT, through its awards program, recognizes individuals who have made significant contributions to the field in research and service. TCS covers a wide variety of topics including algorithms, data structures, computational complexity, parallel and distributed computation, probabilistic computation, quantum computation, automata theory, information theory, cryptography, program semantics and verification, machine learning, computational biology, computational economics, computational geometry, and computational number theory and algebra. Work in this field is often distinguished by its emphasis on mathematical technique and rigor.