Graph Isomorphism

Tuesday, March 11, 2014 - 4:15pm to 5:15pm
3:45pm in 32-G449 (Patil/Kiva)
32-G449 (Patil/Kiva)
Laszlo Babai, University of Chicago

The talk will put recent progress on algorithms for the Graph
Isomorphism (GI) problem in perspective.

GI is one of the very few classical problems in NP of unsettled
complexity status. Shortly after the introduction of group theory
to the algorithmic GI tools [B 1979], a combination of Luks's group
theoretic divide-and-conquer techniques (1980) with Zemlyachenko's
combinatorial degree reduction (1982) resulted in a "moderately
exponential" worst-case bound, exponential in $n^{1/2}$ where $n$
is the number of vertices [B-Luks, STOC 1983]. (I am ignoring
logarithmic terms in the exponent.) This bound has stood firm for
over three decades.

Progress has been made recently on the important subcase of
strongly regular (SR) graphs. The new results, obtained by five
authors, Xi Chen, Xiaorui Sun (Columbia U), and Shang-Hua Teng
(USC), partly in parallel and partly in joint work with the
speaker and his student John Wilmes (U Chicago), reduce the
exponent for SR graphs from $n^{1/3}$ [Spielman, STOC 1996]
to $n^{1/5}$ ([BW] & [CST]: STOC 2013 and [BCSTW]: FOCS 2013).

The result is based partly on an intricate analysis of the
classical combinatorial heuristic of individualization and
refinement (I/R), and partly on a combination of I/R with Luks's
group theoretic methods in the spirit of [B-Luks, 1983] and
[Miller 1983]. More recently, a mathematical obstacle to
potentially subexponentially or even quasipolynomially efficient
applications of the group theory method to SR GI has been removed,
using some spectral graph theory and elementary combinatorics
[B, ITCS 2014]. A caveat: significant combinatorial difficulties
remain in the way of realizing this potential, but promising
first steps appear in the treatment of the low-degree
cases in [BCSTW].

While these results are limited to SR graphs, a class not expected
to be GI-complete, in the speaker's view SR graphs hold some of the
key combinatorial difficulties of the general GI problem.

The talk will review the recent results and put them in perspective
from the point of view of the general GI problem. A key concept
here is that of coherent configurations (CCs), i.e., edge-colorings
of the complete directed graph satisfying certain strong regularity
constraints. These colorings are the stable configurations of the
Weisfeiler--Leman canonical refinement process (1968) and therefore
CCs are GI-complete. *Primitive* CCs are the ones where the obvious
combinatorial divide-and-conquer breaks down. Primitive CCs
generalize SR graphs. Their isomorphism can be tested, using I/R
only, in time, exponential in $n^{1/2}$ [B, Annals of Math 1981].
Breaking this barrier that has stood for a third of a century
is one of the more immediate targets related to the recent work.