The Graph Isomorphism problem is notorious for its unresolved complexity status. There is strong evidence that the problem is not NP-complete, but for over 30 years, the best known worst-case time complexity bound has been exp (O ˜(n 1/2)) (the tilde hides polylogarithmic factors). Strongly regular (SR) graphs have long been viewed as a difficult case for graph isomorphism testing, and have served as a benchmark for progress. We present an algorithm testing isomorphism of SR graphs in time exp (O ˜(n 1/5)), improving the previous best bound of exp (O ˜(n 1/3)) due to Spielman in 1996.

Additionally, we give an exp (O ˜(n 1/3)) time bound for testing isomorphism of primitive coherent configurations (CCs), objects which generalize SR graphs and arise naturally as obstacles to combinatorial divide-and-conquer approaches for general graph isomorphism testing. We furthermore give the first progress in 30 years on an old conjecture of Babai, which states that for all ε>0, every sufficiently large primitive CC with ≥exp (n ε) automorphisms has a primitive automorphism group.

The bulk of our results use probabilistic intuition and methods to analyze the individualization/refinement process. We randomly select a set of vertices which we "individualize'' (assign unique colors); we then "canonically refine'' the coloring, propagating colors in a manner that preserves automorphisms of the colored graph. Efficient isomorphism tests exist whenever this process produces very fine colorings from small individualized sets.

The results on SR graphs are joint with László Babai (STOC'13), and László Babai, Xi Chen, Shang-Hua Teng, and Xiaorui Sun (FOCS'13). The results on primitive CCs are joint with Xiaorui Sun.