Repository logo

Browsing by Author "Collins, Nathaniel A., author"

Filter results by typing the first few letters
Now showing 1 - 1 of 1
  • Thumbnail Image
    ItemOpen Access
    Constant depth circuit complexity for generating quasigroups
    (Colorado State University. Libraries, 2024-07-16) Collins, Nathaniel A., author; Grochow, Joshua A., author; Levet, Michael, author; Weiß, Armin, author; ACM, publisher
    We 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.