Maksim Zhukovskii’s paper was one of 104 papers to be accepted at the prestigious conference which was held in Amsterdam on the 4 - 6 September, 2023.
The accepted papers were split into 3 tracks, or thematic areas, and Maskim’s paper, Canonization of a Random Graph by Two Matrix-Vector Multiplications was judged to be the best paper in his particular track.
The paper suggests a new simple canonical labelling algorithm for typical graphs. Roughly speaking, canonical labelling is a way to give names to vertices of graphs such that vertices of isomorphic graphs receive, in some sense, equal names. As soon as graphs are labelled canonically, the isomorphism problem becomes very easy to solve. It was known (due to Babai, Erdős, Selkow) that there exists an algorithm that efficiently and canonically assigns labels to typical graphs, resulting in efficient distinguishing of these graphs from all the others. Our labelling algorithm is also efficient, its main advantage is its simplicity - it is based solely on basic linear-algebraic primitives: just multiply the vector of degrees by the adjacency matrix of the given graph twice.
Dr Maksim Zhukovskii, a Senior Lecturer in Verification, said: “The European Symposium on Algorithms is a premier algorithmic conference.
“Every year it is co-located with several other events in a combined meeting called ALGO, which is the largest European event devoted to algorithms.
“This award recognises the important role of our growing Foundations of Computation (FOX) research group and its increasing recognition worldwide.”
It is just the latest success for the FOX group, which is one of the largest and most diverse research groups of its type in the UK. Researchers from the group have recently had papers accepted for two of the most prestigious and selective conferences in the field, FOCS 2023 and STOC 2023.