Constant depth circuit complexity for generating quasigroups

DOI10.1145/3666000.3669691MaRDI QIDQ7033545zbMATH OpenFDO

Authors Nathaniel A. Collins, Joshua A. Grochow, Michael Levet, Armin Weiß

Publication date 3 February 2025

zbMATH Keywords

circuit complexityconstant-depth circuitsgroup isomorphismmembership testingminimum generating set\(\mathrm{quasiAC}^0\)quasigroup isomorphism

Mathematics Subject Classification ID

Loops, quasigroups (20N05) Biologically inspired models of computation (DNA computing, membrane computing, etc.) (68Q07)

Cites work

• scientific article; zbMATH DE number 3758564 (Why is no real title available?)
• scientific article; zbMATH DE number 1047205 (Why is no real title available?)
• scientific article; zbMATH DE number 3108440 (Why is no real title available?)
• Algorithms for group isomorphism via group extensions and cohomology
• Complex polynomials and circuit lower bounds for modular counting
• Computing a set of generators of minimal cardinality in a solvable group
• Computing generating sets of minimal size in finite algebras
• Constant depth circuit complexity for generating quasigroups
• Graph isomorphism in quasipolynomial time (extended abstract)
• Graph isomorphism is not \(\mathsf{AC}^{0}\)-reducible to group isomorphism
• Group isomorphism is nearly-linear time for most orders
• Learnability beyond AC ⁰
• Nondeterministics circuits, space complexity and quasigroups
• On limited nondeterminism and the complexity of the V-C dimension
• On the Complexity of Canonical Labeling of Strongly Regular Graphs
• On the Hardness of Graph Isomorphism
• On the \(n\log{n}\) isomorphism technique (preliminary report)
• On the complexity of identifying strongly regular graphs
• On the complexity of some problems on groups input as multiplication tables
• On the parallel complexity of Group Isomorphism via Weisfeiler-Leman
• Oracle branching programs and Logspace versus \(P^*\)
• Proper hierarchies in polylogarithmic time and absence of complete problems
• Strongly regular graphs with smallest eigenvalue -m
• The Cayley semigroup membership problem
• The Complexity of Quasigroup Isomorphism and the Minimum Generating Set Problem
• The isomorphism problem for plain groups is in $\Sigma_3^{\mathsf{P}}$
• The minimum generating set problem
• The theory of nilpotent groups
• Undirected connectivity in log-space

Cited in

(3)

• Constant depth circuit complexity for generating quasigroups
• Complexity of identifying fitting-free groups
• On the constant-depth circuit complexity of generating quasigroups

This page was built for publication: Constant depth circuit complexity for generating quasigroups

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q7033545)