Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model (Youming Qiao)

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.

Time

2017-12-19   15:00 ~ 16:00   

Speaker

Youming Qiao, University of Technology, Sydney

Room

Room 602, School of Information Management & Engineering, Shanghai University of Finance & Economics