Global symmetry from local information: the Graph Isomorphism problem

The Graph Isomorphism (GI) problem is the algorithmic problem to
decide whether or not two given finite graphs are isomorphic.
Recent work by the speaker has brought the worst-case complexity of
this problem down from moderately exponential,
$\exp((n \log n)^{1/2})$ (Luks, 1983) to quasipolynomial
$(\exp((\log n)^c)$, where $n$ is the number of vertices.

We build on Luks’s 1980 divide-and-conquer strategy for the
String Isomorphism problem, a generalization GI, and attack its
bottleneck configuration. At the heart of the algorithm is a lemma
about finite permutation groups that allows us to infer global
symmetry from local information (Local certificates algorithm) and
sets the stage for combinatorial canonical partitioning techniques.