Abstract

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.

Youming Qiao obtained his PhD in computer science from the Institute for Interdisciplinary Sciences, Tsinghua University in 2012. His advisor was Andrew Yao. After working as a postdoc in the Centre for Quantum Technologies, National University of Singapore, he joined the University of Technology Sydney in 2014, and is now a senior lecturer at the Centre for Quantum Software and Information. Youming's research interests lie in computational complexity and algebraic computations.