Weisfeiler—Leman for Group Isomorphism: Action Compatibility

Abstract: 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\"iss\'e 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.

computational complexitycategory theorylogic

Audience: researchers in the topic

---

PALS Panglobal Algebra and Logic Seminar

Series comments: The PALS seminar is a research and learning seminar organized by the algebra and logic research group of the Department of Mathematics at the University of Colorado at Boulder. The scope of the seminar includes all topics with links to algebra, logic, or their applications, like general algebra, logic, model theory, category theory, set theory, set-theoretic topology, or theoretical computer science. Please contact one of the organizers for the Zoom password, to join the mailing list or if you want to speak.

---