Math Colloquium
Speaker: Laszlo Babai, University of Chicago
Title: Global symmetry from local information: the Graph Isomorphism problem
Abstract
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.