Seminar: October 15

John Wilmes, University of Chicago

Faster Canonical Forms for Strongly Regular Graphs

Strongly regular (s.r.) graphs have long been identified as a hard although probably not complete class for the Graph Isomorphism (GI) problem. We show that isomorphism of s.r. graphs with n vertices can be tested in time exp(n^{1/5}) (we ignore logarithmic factors in the exponent), improving the previous exp(n^{1/3}) (Spielman, STOC 1996). One of the novelties is that we make Luks's group theoretic divide-and-conquer methods bear upon the problem via a result of Babai-Luks (1983). The results partly depend on a new "clique geometry" we discover in certain range of the parameters. Another ingredient of the main result is an n^{log n} isomorphism test for Steiner desings; the best previous bound for that case was exp(sqrt{n}) (Babai-Pyber 1994, Spielman 1996).

Joint work with Laszlo Babai and partly simultaneous and partly joint work with Xi Chen, Xiaorui Sun, and Shang-Hua Teng. Presented at STOC'13 (2+3 authors) and FOCS'13 (5 authors). The FOCS paper has been invited to SICOMP's FOCS'13 Special Issue.