Tue, 19 April 2022, 1 pm MDT
The Weisfeiler-Leman (WL) algorithm is a key combinatorial subroutine in Graph Isomorphism, that (for fixed $k \geq 2$) computes an isomorphism invariant coloring of the k-tuples of vertices. Brachter & Schweitzer (LICS 2020) recently adapted WL to the setting of groups. Using a classical Ehrenfeucht-Fraïssé pebble game, we will show that Weisfeiler-Leman serves as a polynomial-time isomorphism test for several families of groups previously shown to be in $\textsf{P}$ by multiple methods. These families of groups include:
(1) Coprime extensions $H \ltimes N$, where $H$ is $O(1)$-generated and the normal Hall subgroup $N$ is Abelian (Qiao, Sarma, & Tang, STACS 2011).
(2) Groups without Abelian normal subgroups (Babai, Codenotti, & Qiao, ICALP 2012).
In both of these cases, the previous strategy involved identifying key group-theoretic structure that could then be leveraged algorithmically, resulting in different algorithms for each family. A common theme among these is that the group-theoretic structure is mostly about the action of one group on another. Our main contribution is to show that a single, combinatorial algorithm (Weisfeiler-Leman) can identify those same group-theoretic structures in polynomial time.
We also show that Weisfeiler-Leman requires only a constant number of rounds to identify groups from each of these families. Combining this result with the parallel WL implementation due to Grohe & Verbitsky (ICALP 2006), this improves the upper bound for isomorphism testing in each of these families from $\textsf{P}$ to $\textsf{TC}^0$.
This is joint work with Joshua A. Grochow.