Count-Free Weisfeiler--Leman and Group Isomorphism

arXiv2212.11247MaRDI QIDQ6507378

Michael Levet, Nathaniel A. Collins

Abstract: We investigate the power of counting in extsc{Group Isomorphism}. We first leverage the count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & Schweitzer, LICS 2020) in tandem with limited non-determinism and limited counting to improve the parallel complexity of isomorphism testing for several families of groups. In particular, we show the following: - Let $G_1$ and $G_2$ be class $2$ $p$-groups of exponent $p$ arising from the CFI and twisted CFI graphs (Cai, F"urer, & Immerman, Combinatorica 1992) respectively, via Mekler's construction (J. Symb. Log., 1981). If the base graph $Gamm{a}_0$ is $3$-regular and connected, then we can distinguish $G_1$ from $G_2$ in $$. This improves the upper bound of $extsf{TC}^1$ from Brachter & Schweitzer (ibid). - Isomorphism testing between an arbitrary group $K$ and a group $G$ with an Abelian normal Hall subgroup whose complement is an $O(1)$-generated solvable group with solvability class poly $loglogn$ is in $$poly $loglogn))$. This notably includes instances where the complement is an $O(1)$-generated nilpotent group. This problem was previously known to be in $extsfP$ (Qiao, Sarma, & Tang, STACS 2011) and $extsfL$ (Grochow & Levet, arXiv 2022). - Isomorphism testing between a direct product of simple groups and an arbitrary group is in $$. This problem was previously shown to be in $extsfL$ (Brachter & Schweitzer, ESA 2022). We finally show that the $q$-ary count-free pebble game is unable to distinguish even Abelian groups. This extends the result of Grochow & Levet (arXiv 2022), who established the result in the case of $q=1$. The general theme is that some counting appears necessary to place extsc{Group Isomorphism} into $extsfP$.

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Applications of logic to group theory (20A15) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Descriptive complexity and finite models (68Q19) Computational methods for problems pertaining to group theory (20-08)

This page was built for publication: Count-Free Weisfeiler--Leman and Group Isomorphism

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6507378)