On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman

Abstract

In this paper, we show that the constant-dimensional Weisfeiler-Leman algorithm for groups (Brachter & Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity upper bounds on isomorphism testing for several families of groups. In particular, we show: - Groups with an Abelian normal Hall subgroup whose complement is $O(1)$-generated are identified by constant-dimensional Weisfeiler-Leman using only a constant number of rounds. This places isomorphism testing for this family of groups into $\text{L}$; the previous upper bound for isomorphism testing was $\text{P}$ (Qiao, Sarma, & Tang, STACS 2011). - We use the individualize-and-refine paradigm to obtain an isomorphism test for groups without Abelian normal subgroups by $\text{SAC}$ circuits of depth $O(\log n)$ and size $n^{O(\log \log n)}$, previously only known to be in $\text{P}$ (Babai, Codenotti, \& Qiao, ICALP 2012) and ${\mathsf{quasiSAC}}^1$ (Chattopadhyay, Torán, \& Wagner, ACM Trans. Comput. Theory, 2013). - We extend a result of Brachter \& Schweitzer (ESA, 2022) on direct products of groups to the parallel setting. Namely, we also show that Weisfeiler--Leman can identify direct products in parallel, provided it can identify each of the indecomposable direct factors in parallel. They previously showed the analogous result for $\text{P}$. We finally consider the count-free Weisfeiler--Leman algorithm, where we show that count-free WL is unable to even distinguish Abelian groups in polynomial-time. Nonetheless, we use count-free WL in tandem with bounded non-determinism and limited counting to obtain a new upper bound of ${\beta }_1{\text{MAC}}^0(\text{FOLL})$ for isomorphism testing of Abelian groups. This improves upon the previous ${\text{TC}}^0(\text{FOLL})$ upper bound due to Chattopadhyay, Torán, \& Wagner (ibid.).

arXiv commentA preliminary version appeared in the proceedings of FCT23. The final journal version has been accepted to the Journal of Computer and System Sciences

References in corpus (7)

• Isomorphism in expanding families of indistinguishable groups
• A fast isomorphism test for groups of genus 2
• Finding direct product decompositions in polynomial time
• The threshold for subgroup profiles to agree is $\Omega (\log n)$
• Canonisation and Definability for Graphs of Bounded Rank Width
• A Systematic Study of Isomorphism Invariants of Finite Groups via the Weisfeiler-Leman Dimension
• The Iteration Number of the Weisfeiler-Leman Algorithm