ARC Colloquium: John Wilmes - University of Chicago

Event Details

Dani Denton
denton at cc dot gatech dot edu



Summary Sentence: MIRC 102 A & B at 1 pm

Full Summary: No summary paragraph submitted.

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)

The Isomorphism Problem for Highly Regular Structures


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.

Additional Information

In Campus Calendar

ARC, College of Computing, School of Computer Science

Invited Audience
Undergraduate students, Faculty/Staff, Public, Graduate students
Algorithm and Randomness Center, ARC, Computational Complexity, Computational Learning Theory, Georgia Tech
  • Created By: Dani Denton
  • Workflow Status: Published
  • Created On: Jan 14, 2016 - 11:13am
  • Last Updated: Apr 13, 2017 - 5:17pm