Room 223, Weber building, 4.15pm (i.e. you can arrive at 4pm for free parking)
with refreshments at 3:30 in WB117.

Michael Levet – UC Boulder

Title: 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. Brac\
hter \& 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 i\
somorphism test for several families of groups previously shown to be in $\textsf{P}$ by multiple methods. These families of groups include:
\begin{itemize}
\item Coprime extensions $H \ltimes N$, where $H$ is $O(1)$-generated and the normal Hall subgroup $N$ is Abelian (Qiao, Sarma, \& Tang, STACS 2011).
\item Groups without Abelian normal subgroups (Babai, Codenotti, \& Qiao, ICALP 2012).
\end{itemize}
\noindent 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$. \\
\noindent This is joint work with Joshua A. Grochow.