Constant Depth Circuit Complexity for 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 <Formula format="inline"><TexMath><?TeX AC?></TexMath><AltText>Math 1</AltText><File name="issac24-21-inline1" type="svg"/></Formula> 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 <Formula format="inline"><TexMath><?TeX AC?></TexMath><AltText>Math 2</AltText><File name="issac24-21-inline2" type="svg"/></Formula> circuits of depth O(log log n) using O(log 2n) nondeterministic bits, a class we denote <Formula format="inline"><TexMath><?TeX ∃ ^log ²nFOLL?></TexMath><AltText>Math 3</AltText><File name="issac24-21-inline3" type="svg"/></Formula>. We narrow this gap by improving the upper bound for these problems to <Formula format="inline"><TexMath><?TeX quasiAC⁰?></TexMath><AltText>Math 4</AltText><File name="issac24-21-inline4" type="svg"/></Formula>, thus decreasing the depth to constant.