*********************************
There is now a CONTENT FREEZE for Mercury while we switch to a new platform. It began on Friday, March 10 at 6pm and will end on Wednesday, March 15 at noon. No new content can be created during this time, but all material in the system as of the beginning of the freeze will be migrated to the new platform, including users and groups. Functionally the new site is identical to the old one. webteam@gatech.edu
*********************************
Algorithms & Randomness Center (ARC)
John Wilmes – University of Chicago
Monday, January 25, 20116
MiRC 102 A & B - 1:00 pm
(Refreshments will be served in Klaus 2222 at 2 pm)
Title:
The Isomorphism Problem for Highly Regular Structures
Abstract:
The Graph Isomorphism (GI) problem has been notorious in computational complexity theory for its unresolved complexity status. Until Babai's recently announced quasipolynomial-time algorithm for GI, the worst-case time-complexity bound of $\exp(\tilde{O}(n^{1/2}))$ where $n$ is the number of vertices (Babai--Luks, 1983), had stood for over 30 years.
Among the obstacles Babai confronts in his recent breakthrough are primitive coherent configurations (PCCs), a class of highly-regular structures generalizing strongly regular graphs. In this talk, we will describe recent progress characterizing the structure and automorphism groups of PCCs and other highly-regular structures, with applications to GI, and we will describe the connections between these results and Babai's breakthrough.
In particular, in joint work with Sun, we classify the PCCs with the most automorphisms. In joint work with Babai, Chen, Sun, and Teng, we give the first quasipolynomial-time algorithm for strongly regular GI over an entire interval of the exponent of the degree parameter. And in joint work with Babai, we give a $n^{O(\log n)}$-time algorithm for the important special case of Steiner Design Isomorphism. In all cases, our progress relies on new structural results we prove, especially on new bounds for the rate of expansion of small sets.
