Math Colloquium - Laszlo Babai, University of Chicago

Event time: 
Wednesday, February 15, 2017 - 4:15pm
215 LOM See map
12 Hillhouse Avenue
New Haven, CT 06511
Event description: 

Math Colloquium

Speaker: Laszlo Babai, University of Chicago

Title: 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.