On the Constant-Depth Circuit Complexity of Generating Quasigroups

We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for groups and quasigroups (=Latin squares), given as input in terms of their multiplication (Cayley) tables. Despite decades of research on these problems, lower bounds for these problems even against depth-$2$ AC circuits remain unknown. Perhaps surprisingly, Chattopadhyay, Torán, and Wagner (FSTTCS 2010; ACM Trans. Comput. Theory, 2013) showed that Quasigroup Isomorphism could be solved by AC circuits of depth O(log log n) using O(log² n) nondeterministic bits, a class we denote ∃log²(n)FOLL. We narrow this gap by improving the upper bound for many of these problems to quasiAC⁰, thus decreasing the depth to constant. In particular, we show: - MGS for quasigroups is in ∃log²(n)∀log nNTIME(polylog(n))⊆ quasiAC⁰. Papadimitriou and Yannakakis (J. Comput. Syst. Sci., 1996) conjectured that this problem was ∃log²(n)P-complete; our results refute a version of that conjecture for completeness under quasiAC⁰ reductions unconditionally, and under polylog-space reductions assuming EXP ≠ PSPACE. - MGS for groups is in AC¹(L), improving on the previous upper bound of P (Lucchini & Thakkar, J. Algebra, 2024). - Quasigroup Isomorphism belongs to ∃log²(n)AC⁰(DTISP(polylog,log)⊆ quasiAC⁰, improving on the previous bound of ∃log²(n)L∩∃log²(n)FOLL⊆ quasiFOLL (Chattopadhyay, Torán, & Wagner, ibid.; Levet, Australas. J. Combin., 2023). Our results suggest that understanding the constant-depth circuit complexity may be key to resolving the complexity of problems concerning (quasi)groups in the multiplication table model. 39 pages. This is the TheoretiCS journal version