Parallel Algorithms for Group Isomorphism via Code Equivalence
For complexity theorists, this work refines the parallel complexity of group isomorphism for specific families, achieving AC^3 instead of P, and improves the depth bound for central-radical groups.
The authors present AC^3 isomorphism tests for two families of groups (coprime extensions and central-radical groups), improving previous polynomial-time results by implementing Linear Code Equivalence in AC^3. They also show that isomorphism of arbitrary central-radical groups is decidable in AC circuits of depth O(log^3 n) and size n^{O(log log n)}, improving the previous n^{O(log log n)}-time bound.
In this paper, we exhibit $\textsf{AC}^{3}$ isomorphism tests for coprime extensions $H \ltimes N$ where $H$ is elementary Abelian and $N$ is Abelian; and groups where $\text{Rad}(G) = Z(G)$ is elementary Abelian and $G = \text{Soc}^{*}(G)$. The fact that isomorphism testing for these families is in $\textsf{P}$ was established respectively by Qiao, Sarma, and Tang (STACS 2011), and Grochow and Qiao (CCC 2014, SIAM J. Comput. 2017). The polynomial-time isomorphism tests for both of these families crucially leveraged small (size $O(\log |G|)$) instances of Linear Code Equivalence (Babai, SODA 2011). Here, we combine Luks' group-theoretic method for Graph Isomorphism (FOCS 1980, J. Comput. Syst. Sci. 1982) with the fact that $G$ is given by its multiplication table, to implement the corresponding instances of Linear Code Equivalence in $\textsf{AC}^{3}$. As a byproduct of our work, we show that isomorphism testing of arbitrary central-radical groups is decidable using $\textsf{AC}$ circuits of depth $O(\log^3 n)$ and size $n^{O(\log \log n)}$. This improves upon the previous bound of $n^{O(\log \log n)}$-time due to Grochow and Qiao (ibid.).