STOC 2017 Theory Fest: Best paper award

04 May 2017
Professor Cristian Calude and Professor Bakhadyr Khoussainov

Professor Cristian Calude and Professor Bakh Khoussainov, from the Department of Computer Science, have won one of the most prestigious awards in theoretical computer science worldwide.

Their joint paper entitled Deciding parity games in quasi-polynomial time, saw them working alongside S Jain, W Li and F Stephan from the National University of Singapore, and together they won the best paper award at the Symposium on Theory of Computation (STOC). The group will be presented with the award at the 49th Annual ACM STOC 2017 symposium held in Montreal in June.

The paper solves a long standing open problem that goes back to the 1970s, related to verification, model checking, logic, automata, and mu-calculus. According to L Aceto, past President of the European Association for Theoretical Computer Science, "This is indeed a major breakthrough on a very important problem" – a problem that has “foiled many well-known experts in the area”, adds Bakh.

STOC is also where Gödel prize and Knuth prize winners are awarded. Out of 422 submissions toward the award, the STOC accepted 102 with Cris and Bakh’s paper being the first paper to be accepted that is written by New Zealand computer scientists and mathematicians.

“It is a good example of fruitful research collaboration between the University of Auckland and the National University of Singapore,” says Bakh.

STOC 2017 Theory Fest