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.

 

 

About valuevar

I am a number theorist with side interests in combinatorics and group theory.
This entry was posted in Uncategorized and tagged , , , . Bookmark the permalink.

11 Responses to Graph isomorphism in subexponential time

  1. Pingback: Early january 2017 items | episodic thoughts

  2. Pingback: On exp(exp(sqrt(log n))) algorithms. | Windows On Theory

  3. Pingback: Helfgott finder fejl i Babais artikel om grafisomorfiproblemet | Matematikbloggen på AAU

  4. Bogdan Grechuk says:

    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?

  5. valuevar says:

    (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.

  6. Pingback: La complejidad del isomorfismo de grafos sigue siendo subexponencial | Ciencia | La Ciencia de la Mula Francis

  7. Pingback: Babai Strikes Back | A bunch of data

  8. DR says:

    Have you been given a look at Babai’s new argument purportedly fixing the gap?

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s