11 citations · 25 across the 18 of their papers we have counts for
5 papers · 1 filter
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…
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…
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…
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 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…