CIRCA lunchtime seminar

Speaker: Jendrik Brachter (TU Darmstadt)

Title: Approaching the group isomorphism problem via the Weisfeiler-Leman algorithm

Abstract: The group isomorphism problem, i.e., deciding whether two given finite groups are isomorphic, remains one of the most fundamental problems in computational group theory for which we currently do not have efficient algorithmic methods at hand. In fact our understanding of the problem's complexity is almost entirely limited to special group classes, whereas in the general case, apart from minor improvements, we are stuck with the n^O(log n) bound obtained from enumerating all log-sized generating sets.

Inspired from the theory of the graph isomorphism problem, we devise and analyze a Weisfeiler-Leman (WL) algorithm for finite groups. For graphs, the WL-algorithm is a crucial subroutine in all state-of-the-art graph isomorphism solvers and it forms an important building block in Babai's famous quasi-polynomial time algorithm for graph isomorphism. It is a combinatorial tool that assigns canonical colorings to graphs. It thereby serves as a non-isomorphism test, with important connections to logic, games and graph structure theory.

In the talk, I give a gentle introduction to the WL-algorithm and I show how to transfer it to the setting of groups. Then I present recent work (joined with Pascal Schweitzer), discussing the distinguishing power of WL on finite groups and its deep connections to group structure theory. It turns out that the WL-algorithm implicitly captures a surprising number of group-theoretic properties, including nilpotency, solubility or composition factors.