Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time I: The "Local Certificates Algorithm" (Combinatorics and TCS seminar)
The talk has been moved to a different location: Kent 120
In a series of two talks we outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylog n)) time.
The best previous bound for GI was exp(sqrt{n log n}), where n is the number of vertices (Luks, 1983). For SI and CI the best previous bound was similar, exp(sqrt{n}(log n)^c), where n is the size of the permutation domain (the speaker, 1983).
In this first talk we give an overview of the algorithm and present the core group-theoretic divide-and-conquer routine, the "Local Certificates algorithm." Familiarity with undergraduate-level group theory will be assumed.
Refreshments will be served after the talk in Ry 255.
