Jendrik Brachter\
    TU Kaiserslautern\
- |
    Pascal Schweitzer\
    TU Kaiserslautern\
bibliography:
- '../refs.bib'
title: 'On the Weisfeiler-Leman Dimension of Finite Groups'
---

Introduction
============

The notion of isomorphisms between finite groups remains one of the most basic concepts of group theory for which we do not have efficient algorithmic tools. The algorithmic Group Isomorphism Problem formalizes the task of deciding whether two given (finite) groups are isomorphic, but in fact, we do not understand its complexity. We have neither a polynomial time algorithm for testing isomorphism, nor complexity theoretic evidence indicating to us that the problem is not polynomial time solvable. Considering groups of order $n$, a simple approach, attributed to Tarjan in [@Mi78], is to pick a small generating set in one of the groups and to check for all possible images of the generators in the other group, whether the partial map extends to an isomorphism. This approach gives us a worst-case runtime of $n^{\log t+\mathcal{O}(1)}$ where $t$ is the size of the generating set. Since every group of order $n$ has a generating set of size at most $\log n$, this yields $n^{\log n+\mathcal{O}(1)}$ in the worst case. Despite decades of active research this bound has seen 