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.