The average-case complexity of the Word Problem for groups of matrices over $\mathbb{Z}$ is linear

Frédérique Bassino, Cyril Nicaud, Pascal Weil

We show that the Word Problem in finitely generated subgroups of ${\text{GL}}_d(\mathbb{Z})$ can be solved in linear average-case complexity. This is done under the bit-complexity…