Collins, Nathaniel A., authorGrochow, Joshua A., authorLevet, Michael, authorWeiß, Armin, authorACM, publisher2024-11-112024-11-112024-07-16Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, and Armin Weiß. 2024. Constant Depth Circuit Complexity for Generating Quasigroups. In International Symposium on Symbolic and Algebraic Computation (ISSAC '24), July 16–19, 2024, Raleigh, NC, USA. ACM, New York, NY, USA, Article 111, 10 pages. https://doi.org/10.1145/3666000.3669691https://hdl.handle.net/10217/239515We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(qasi)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(log2 n) nondeterministic bits, a class we denote ∃log2 nFOLL. We narrow this gap by improving the upper bound for these problems to quasiAC0, thus decreasing the depth to constant. In particular, we show that Membership can be solved in NTIME(polylog(n)) … 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.born digitalarticleseng©Nathaniel A. Collins, et al. ACM 2024. This is the author's version of the work. It is posted here for your personal use. Not for redistribution. The definitive Version of Record was published in ISSAC '24, https://dx.doi.org/10.1145/3666000.3669691.group isomorphismquasigroup isomorphismminimum generating setmembership testingconstant-depth circuitsquasiAC0circuit complexityTexthttps://doi.org/10.1145/3666000.3669691