We consider the algorithmic problem of testing isomorphism of finite p-groups of class 2 and exponent p. We propose to view this problem as a linear algebraic analogue of graph isomorphism. This allows us to transfer ideas and techniques developed for graph isomorphism to this hard instance of group isomorphism. Inspired by the first average-case efficient algorithm for graph isomorphism by Babai, Erd?s, and Selkow in 1980, we devise an average-case algorithm for this problem that runs in time polynomial in the group order. The average-case analysis is done in a random model which is a linear algebraic analogue of the Erd?s-Renyi model for random graphs. For this, we develop a linear algebraic analogue of the classical individualisation technique, a technique belonging to a set of combinatorial techniques that has been critical for the progress on the worst-case time complexity for graph isomorphism, but was missing in the group isomorphism context.

This talk is based on a joint work with Yinan Li, and the arXiv ref is 1708.04501.