4 papers · 1 filter
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 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…
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…
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…