Graph isomorphism in subexponential time

In the course of preparing my Bourbaki talk on Babai’s work on the graph isomorphism problem, I found an error. It is serious. Babai has succeeded in recovering a result that, while weaker, is still remarkable.

Preparing a Bourbaki talk implies (a) going through somebody else’s work in great detail, and (b) preparing an expository paper on the subject. My exposition of Babai’s work is ready and will be publicly available in the next few days. It is a complete walkthrough of the proof, and should allow others to verify, as I did, that the modified version is correct.

Here is an excerpt from my introduction (in French in the original):

“Thm 1.1 (Babai) .- The string isomorphism problem can be solved in time exp(exp(O(sqrt(log n log log n)))) for strings of length n.

It is clear that the bound here is sub-exponential, but not quasipolynomial. In November 2015, Babai announced a solution in quasipolynomial time, with an explicit algorithm. The process of preparing this expository work confirmed that the algorithm was correct, or easily repairable, but it also made me realize that the time analysis was incorrect. The version announced here is correct.

Thm. 1.2 (Babai).- The graph isomorphism problem can be solved in time exp(exp(O(sqrt(log n log log n)))), where n is the number of vertices.

Our main references will be [Babai’s 2015 preprint and his extended abstract at STOC 2016]. We will attempt to examine the proof in as much detail as an expository work of this format allows, in part to help eliminate any doubt that may remain on the current form of the result. The error lay in a part of the proof that can be isolated and corrected, and might be later improved on its own (“Split or Johnson”). The rest of the work – rich in innovative ideas – is still valid.”

See also Laci Babai’s own announcement on the subject:

http://people.cs.uchicago.edu/~laci/update.html

Update (Jan 14): As many of you know, Babai posted last Monday that he had fixed the problem. This is just to tell you that (a) his fix is correct (and elegant), (b) I have spent the last five days checking other things in the proof and making some bits explicit. I can now state with assurance that the proof is correct: Babai is now giving an algorithm that works in quasipolynomial time. See the video of my Bourbaki talk at https://www.youtube.com/watch?v=7NR975OM2G8&list=PL9kd4mpdvWcCN64K5VhaYFH_gBa-WlIr3&index=1

I will put up the corresponding expository article soon.