We show that there is a dense set of group orders such that for every such order we can decide in nearly-linear time whether two multiplication tables describe isomorphic groups. This improves significantly over the general quasi-polynomial time complexity and shows that group isomorphism can be tested efficiently for almost all group orders. We also show that in nearly-linear time it can be decided whether a multiplication table describes a group; this improves over the known super-linear complexity. Our complexities are calculated for a deterministic multi-tape Turing machine model, but we give the implications to a RAM model in the promise hierarchy as well.

Motivated by testing isomorphism of p-groups, we study the alternating matrix space isometry problem (AltMatSpIso), which asks to decide whether two m-dimensional subspaces of n×n alternating (skew-symmetric if the field is not of characteristic 2) matrices are the same up to a change of basis. Over a finite field F_p with some prime p≠2, solving AltMatSpIso in time p^O(n+m) is equivalent to testing isomorphism of p-groups of class 2 and exponent p in time polynomial in the group order. The latter problem has long been considered a bottleneck case for the group isomorphism problem. Recently, Li and Qiao presented an average-case algorithm for AltMatSpIso in time p^O(n) when n and m are linearly related (FOCS '17). In this paper, we present an average-case algorithm for AltMatSpIso in time p^O(n+m). Besides removing the restriction on the relation between n and m, our algorithm is considerably simpler, and the average-case analysis is stronger. We then implement our algorithm, with suitable modifications, in Magma. Our experiments indicate that it improves significantly over default (brute-force) algorithms for this problem.