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.