11 citations · 25 across the 18 of their papers we have counts for
19 papers
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 Parallel Complexity of Identifying Groups and Quasigroups via Decompositions
Dan Johnson, Michael Levet, Petr Vojtěchovský +1
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…
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…
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…
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 Descriptive Complexity of Groups without Abelian Normal Subgroups (Extended Abstract)
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-Fraisse bijective pebble game in Hella's (Ann. Pure Ap…
Canonizing Graphs of Bounded Rank-Width in Parallel via Weisfeiler--Leman
Michael Levet, Puck Rombach, Nicholas Sieger
In this paper, we show that computing canonical labelings of graphs of bounded rank-width is in . Our approach builds on the framework of Köbler & Verbitsky (CSR 2…
Moments of Colored Permutation Statistics on Conjugacy Classes
Jesse Campion Loth, Michael Levet, Kevin Liu +2
In this paper, we consider the moments of statistics on conjugacy classes of the colored permutation groups . We first show that…
Complexity and Enumeration in Models of Genome Rearrangement
Lora Bailey, Heather Smith Blake, Garner Cochran +8
In this paper, we examine the computational complexity of enumeration in certain genome rearrangement models. We first show that the Pairwise Rearrangement problem in the Single Cu…
Permutation Statistics in Conjugacy Classes of the Symmetric Group
Jesse Campion Loth, Michael Levet, Kevin Liu +3
We introduce the notion of a weighted inversion statistic on the symmetric group, and examine its distribution on each conjugacy class. Our work generalizes the study of several co…
Count-Free Weisfeiler--Leman and Group Isomorphism
Nathaniel A. Collins, Michael Levet
We investigate the power of counting in Group Isomorphism. We first leverage the count-free variant of the Weisfeiler--Leman Version I algorithm for groups (Brachter & Schweitzer,…
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 A…
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…
Experience Report: Standards-Based Grading at Scale in Algorithms
Lijun Chen, Joshua A. Grochow, Ryan Layer +1
We report our experiences implementing standards-based grading at scale in an Algorithms course, which serves as the terminal required CS Theory course in our department's undergra…
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…
Improved bounds on the size of the smallest representation of relation algebra
Jeremy F. Alm, Michael Levet, Saeed Moazami +4
In this paper, we shed new light on the spectrum of the relation algebra we call , which is obtained by splitting the non-flexible diversity atom of into symmetr…
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…
Directed Ramsey and Anti-Ramsey Schemes and the Flexible Atom Conjecture
Jeremy F. Alm, Michael Levet
In this paper, we shed new light on the Flexible Atom Conjecture. We first give finite representation results for relation algebras , , , $80_{8…