Quanta on Graph Isomorphism

I think the best casual-reader coverage of Babai's new finding, so far, is this article on Quanta: Landmark Algorithm Breaks 30-Year Impasse.

One of my favorite parts is the section where the author discusses Babai's patience and perseverance:

Babai’s proposed algorithm doesn’t bring graph isomorphism all the way into P, but it comes close. It is quasi-polynomial, he asserts, which means that for a graph with n nodes, the algorithm’s running time is comparable to n raised not to a constant power (as in a polynomial) but to a power that grows very slowly.

The previous best algorithm — which Babai was also involved in creating in 1983 with Eugene Luks, now a professor emeritus at the University of Oregon — ran in “subexponential” time, a running time whose distance from quasi-polynomial time is nearly as big as the gulf between exponential time and polynomial time. Babai, who started working on graph isomorphism in 1977, “has been chipping away at this problem for about 40 years,” Aaronson said.

Babai's paper is up on Arxiv: Graph Isomorphism in Quasipolynomial Time. Although this is definitely not for the casual student, it's a remarkably clear paper, systematically working its way through the problem in detail.

As Babai notes near the end of the paper, in this area of Computer Science, theory and practice have taken different paths:

The purpose of the present paper is to give a guaranteed upper bound (worst-case analysis); it does not contribute to practical solutions. It seems, for all practical purposes, the Graph Isomorphism problem is solved; a suite of remarkably efficient programs is available (nauty, saucy, Bliss, conauto, Traces). The article by McKay and Piperno [McP] gives a detailed comparison of methods and performance. Piperno’s article [Pi] gives a detailed description of Traces, possibly the most successful program for large, difficult graphs.

The article on Traces is here: Search Space Contraction in Canonical Labeling of Graphs. The description of the backtrack construction on page 7 is accompanied by beautiful full-color diagrams; a picture is truly worth thousands of words here.

Lastly, the first of the four explanatory talks given by Babai at the U of C is available on YouTube.