Constant Depth Circuit Complexity for Generating Quasigroups
Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß · 2024
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 Math 1 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 Math 2 circuits of depth O(log log n) using O(log 2n) nondeterministic bits, a class we denote Math 3 . We narrow this gap by improving the upper bound for these problems to Math 4 , thus decreasing the depth to constant.