9 papers
Complexity of Constructing Minimal Faithful Permutation Representations for Fitting-free Groups
Michael Levet, Pranjal Srivastava, Dhara Thakkar
In this paper, we investigate the complexity of computing minimal faithful permutation representations for groups without abelian normal subgroups (a.k.a. Fitting-free groups). Whe…
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 Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
Dan Johnson, Michael Levet, Petr VojtÄchovský +2
In this paper, we investigate the computational complexity of isomorphism testing for finite groups and quasigroups, given by their multiplication tables. We crucially take advanta…
Comer Schemes, Relation Algebras, and the Flexible Atom Conjecture
Jeremy F. Alm, David A. Andrews, Michael Levet
In this paper, we consider relational structures arising from Comer's finite field construction, where the cosets need not be sum free. These Comer schemes generalize the notion of…
On the Descriptive Complexity of Groups without Abelian Normal Subgroups
Joshua A. Grochow, Michael Levet
In this paper, we explore the descriptive complexity theory of finite groups by examining the power of the second Ehrenfeucht--Fraïssé bijective pebble game in Hella's (Ann. Pure…
On the Parallel Complexity of Group Isomorphism via Weisfeiler-Leman
Joshua A. Grochow, Michael Levet
In this paper, we show that the constant-dimensional Weisfeiler-Leman algorithm for groups (Brachter & Schweitzer, LICS 2020) can be fruitfully used to improve parallel complexity…