Dr Maksim Zhukovskii, Senior Lecturer in Verification here at the School of Computer Science at the University of Sheffield, has received one of theoretical computer science’s highest honours, having been awarded the Best Paper Award (Track A: Algorithms, Complexity, and Games) at the 53rd International Colloquium on Automata, Languages and Programming (ICALP), held at Royal Holloway, University of London.
The paper itself, titled "Canonical Labelling of Random Regular Graphs" addresses the canonical labelling of graphs, which is a fundamental task in computer science intimately linked to the famous graph isomorphism problem: determining whether two networks or structures are identical despite being labeled or arranged differently.
The research was carried out in collaboration with an international team of leading mathematicians and computer scientists including:
- Mikhail Isaev (UNSW Sydney)
- Tamás Makai (University of Munich)
- Brendan McKay (Australian National University)
- Paweł Prałat (Toronto Metropolitan University)
- Jane Tan (University of Oxford)
While identifying structural equivalences sounds straightforward, doing so efficiently has long posed a significant computational challenge. The main result of the paper reveals that almost all regular graphs can be canonically labelled using colour refinement, which overall provides a simple, fast, and lightweight algorithmic technique.
Dr Zhukovskii said: "It is a great honour to receive the ICALP Best Paper Award. This work brings together ideas from random graph theory, combinatorics, and algorithms, and shows that a surprisingly simple procedure can solve the fundamental graph isomorphism problem for almost all regular graphs. I am particularly pleased to see these ideas recognised by the theoretical computer science community."
ICALP itself is widely recognised as the leading European conference in theoretical computer science and takes place yearly. More information about this year's conference can be found here.