11 citations · 25 across the 18 of their papers we have counts for
5 papers · 1 filter
Group Isomorphism and the Polylogarithmic-Time Hierarchy: Depth-2 Circuits and Lower Bounds
Joshua A. Grochow, Gülce Kardeş, Michael Levet
In this paper, we investigate the low-depth circuit complexity of Group Isomorphism in the multiplication (Cayley) table model. We prove the first circuit lower bounds for Group Is…
Parallel Algorithms for Group Isomorphism via Code Equivalence
Michael Levet
In this paper, we exhibit isomorphism tests for coprime extensions where is elementary Abelian and is Abelian; and groups where $\text{Rad}(…
On the Complexity of Identifying Groups without Abelian Normal Subgroups: Parallel, First Order, and GI-Hardness
Joshua A. Grochow, Dan Johnson, Michael Levet
In this paper, we exhibit an isomorphism test for groups without Abelian normal subgroups (a.k.a. Fitting-free groups), a class for which isomorphism testing was…
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…
On the Complexity of Identifying Strongly Regular Graphs
Michael Levet
In this paper, we show that Graph Isomorphism (GI) is not -reducible to several problems, including the Latin Square Isotopy problem, isomorphism testing of severa…