2016 Theses Doctoral

On the isomorphism testing of graphs

Sun, Xiaorui

Graph Isomorphism is one of the very few classical problems in NP of unsettled complexity status. The families of highly regular structures, for example Steiner 2-designs, strongly regular graphs and primitive coherent configurations, have been perceived as difficult cases for graph isomorphism. These highly regular structures arise naturally as obstacles for both the classical group theory and combinatorial approaches for the graph isomorphism problem.
In this thesis we investigate the isomorphism problem of highly regular structures. We present new results to understand the combinatorial structure of highly regular structures, and propose some new algorithms to compute the canonical forms (and thus isomorphism testing) of highly regular structures based on the structural theorems.
We also give an algorithm solving the isomorphism problem of two unknown graphs in the property testing setting. Our new algorithm has sample complexity matching the information theoretical lower bound up to some multiplicative subpolynomial factor.