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.

Files

  • thumnail for Sun_columbia_0054D_13531.pdf Sun_columbia_0054D_13531.pdf application/pdf 1.11 MB Download File

More About This Work

Academic Units
Computer Science
Thesis Advisors
Chen, Xi
Degree
Ph.D., Columbia University
Published Here
September 6, 2016