Parallel Algorithms for Group Isomorphism via Code Equivalence

In this paper, we exhibit AC³ isomorphism tests for coprime extensions H ⋉ N where H is elementary Abelian and N is Abelian; and groups where Rad (G) = Z (G) is elementary Abelian and G = Soc^* (G). The fact that isomorphism testing for these families is in 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 AC³. As a byproduct of our work, we show that isomorphism testing of arbitrary central-radical groups is decidable using AC circuits of depth O (log³ 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. ).