http://www.johnwilmes.name/

AG 1, AG 2, AG 3, AG 4, AG 5, RG1, SWS, MMCI   Info

AG Audience

English

30 Minutes

Saarbrücken

The Graph Isomorphism problem has been notorious in computational
complexity theory for its unresolved complexity status. Families of
graphs characterized by high degrees of regularity, such as strongly
regular graphs (SRGs), have been viewed as particularly difficult cases.
In joint work with Babai, Chen, Sun, and Teng, we give new
time-complexity bounds for SRG Isomorphism, including the first
quasipolynomial bound in a range of the parameters. Our overall
exp(O~(n^{1/5})) time-complexity bound improved Spielman’s
exp(O~(n^{1/3})) time-complexity bound established in 1996.

Primitive coherent configurations (PCCs) generalize SRGs. PCCs appear in
Babai’s recent quasipolynomial-time algorithm for Graph Isomorphism as
combinatorial obstacles that must be overcome. In joint work with Sun,
we give an exp(O~(n^{1/3}))-time algorithm for PCC Isomorphism,
improving the previous best exp(O~(n^{1/2}))-time algorithm, due to
Babai in 1981.

In this talk, we will give an overview of progress on the isomorphism
problem for highly regular combinatorial objects, explain some of the
combinatorial structure theory underlying our analysis, and describe the
connections between these results and Babai’s recent breakthrough.

Christina Fries

--email hidden

passcode not visible

logged in users only