Babai Strikes Back

"So it is quasipolynomial time again"

Short Version: Babai fixed his proof.

In November 2015 László Babai announced a talk "Graph Isomorphism in Quasipolynomial Time" at the University of Chicago, an incredible breakthrough for this important problem. The algorithm is a tour-de-force masterpiece combining combinatorics and group theory. The result sent shock waves through the community, we covered the result as did most everyone else, despite Babai's disclaimer that the result was not yet peer reviewed.

Robin Thomas at Georgia Tech immediately suggested we get Babai down to Atlanta to talk on the paper. Babai's dance card filled up quickly but he eventually agreed to give two talks at Georgia Tech. January 9-10, 2017, right after the Joint Mathematics Meeting in Atlanta. Robin scheduled the 25th anniversary celebration of our Algorithms, Combinatorics and Optimization PhD program around Babai's talks.

Around 4 AM last Wednesday we got a lengthy email from Babai with the subject "new development" and the first line "The GI algorithm does not run in quasipolynomial time." The email explained the new running time, still a huge breakthrough being the first subexponential time algorithm for graph isomorphism, but not as strong as before. Harald Helfgott had discovered the problem while going through the proof carefully preparing for a Bourbaki seminar talk on the result. The email asked if we still wanted him to give the talk (of course we did) and instructions for removing "quasipolynomial" from his talk abstracts. That email must have been very hard for Babai to write.

Babai posted an update on his home page which I too quickly tweeted. News spread quickly in blog posts and by Thursday an online article in Quanta titled Complexity Theory Strikes Back. Scott Aaronson picked a lousy day to release his new book-length survey on the P v NP problem.

On top of all this snow in Atlanta threatened to cancel the Monday talk. But the snow never came and Babai started his talk at 4:30 PM to a packed room. Without telling any of us beforehand, an hour earlier he had posted an update to his update and announced it in his talk.

We were watching history. From the talk I tweeted the new news though Bill Cook, also in the audience, beat me to the punch. Babai went on to describe the issue, an error in the analysis of the running time in the recursion, and the fix, basically a way to avoid that recursive step, but I can't do it justice here. At the end he proclaimed "So it is quasipolynomial time again". And so it was.

Today Babai talked about the group theory behind the algorithm as though there was never an issue in the first place.