Repository logo
 

Constant depth circuit complexity for generating quasigroups

Simple item page
dc.contributor.authorCollins, Nathaniel A., author
dc.contributor.authorGrochow, Joshua A., author
dc.contributor.authorLevet, Michael, author
dc.contributor.authorWeiß, Armin, author
dc.contributor.authorACM, publisher
dc.date.accessioned2024-11-11T19:30:35Z
dc.date.available2024-11-11T19:30:35Z
dc.date.issued2024-07-16
dc.description.abstractWe 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.
dc.format.mediumborn digital
dc.format.mediumarticles
dc.identifier.bibliographicCitationNathaniel 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.3669691
dc.identifier.doihttps://doi.org/10.1145/3666000.3669691
dc.identifier.urihttps://hdl.handle.net/10217/239515
dc.languageEnglish
dc.language.isoeng
dc.publisherColorado State University. Libraries
dc.relation.ispartofPublications
dc.relation.ispartofACM DL Digital Library
dc.rights©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.
dc.subjectgroup isomorphism
dc.subjectquasigroup isomorphism
dc.subjectminimum generating set
dc.subjectmembership testing
dc.subjectconstant-depth circuits
dc.subjectquasiAC0
dc.subjectcircuit complexity
dc.titleConstant depth circuit complexity for generating quasigroups
dc.typeText

Files

Original bundle
Now showing 1 - 1 of 1
Thumbnail Image
Name:
FACF_ACMOA_3666000.3669691.pdf
Size:
600.95 KB
Format:
Adobe Portable Document Format
Download

Collections

Publications