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:
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.
Pingback: Early january 2017 items | episodic thoughts
Pingback: On exp(exp(sqrt(log n))) algorithms. | Windows On Theory
Pingback: Helfgott finder fejl i Babais artikel om grafisomorfiproblemet | Matematikbloggen på AAU
Will your exposition be in English? (Sorry, I do not speak French).
Also, unrelated question – are you going to publish your proof of The ternary Goldbach conjecture in a journal?
(a) The expository paper is in French. I’ll put it up in the arxiv in a few days.
(b) The proof will appear as a volume in Ann. of Math. Studies. I’m rewriting it as an advanced textbook, essentially.
Pingback: La complejidad del isomorfismo de grafos sigue siendo subexponencial | Ciencia | La Ciencia de la Mula Francis
Pingback: Babai Strikes Back | A bunch of data
Have you been given a look at Babai’s new argument purportedly fixing the gap?
Of course I have. I am going through the overall argument one last time, making sure that everything is in place.
It’s fine. I hope to be able to put the talk’s text very soon.
Thanks! Your efforts on this are monumental and much appreciated.
One more paper on graph isomorphism in quasipolynomial time: https://arxiv.org/abs/1607.00547v1
Interesting. Why hadn’t we heard about this? What is this “SAG” problem exactly, and how does it help with graph isomorphism problem?
Pingback: Laci Babai Visits Israel! | Combinatorics and more