Showing cs.CCShow all
2 papers · 1 filter
cs.CC2024
On the Constant-Depth Circuit Complexity of Generating Quasigroups
Nathaniel A. Collins, Joshua A. Grochow, Michael Levet +1
We investigate the constant-depth circuit complexity of the Isomorphism Problem, Minimum Generating Set Problem (MGS), and Sub(quasi)group Membership Problem (Membership) for group…
cs.CC2023
Violating Constant Degree Hypothesis Requires Breaking Symmetry
Piotr Kawałek, Armin Weiß
The Constant Degree Hypothesis was introduced by Barrington et. al. (1990) to study some extensions of -groups by nilpotent groups and the power of these groups in a certain com…