2017-12-19 | Youming Qiao: Linear Algebraic Analogues of the Graph Isomorphism Problem and the Erdős-Rényi Model



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.


2017年12月19日(周二) 15:00-16:00


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.


信息管理与工程学院  602室