Credit: Martin Grandjean, via Wikimedia.
That plucky graph isomorphism problem is at it again! In November 2015, University of Chicago computer scientist Laszlo Babai announced an algorithm to determine whether two graphs are isomorphic in quasipolynomial time, and there was much rejoicing. (My co-blogger Anna Haensch covered it here at the time.)
But earlier this month, University of Göttingen and CNRS mathematician Harald Helfgott posted on his blog that he had found an error in the proof, and it looked to be a major one. Babai’s algorithm was still a big improvement over earlier algorithms but only ran at subexponential rather than quasipolynomial time. (Complexity jargon got your head spinning? Check out Jeremy Kun’s primers on Big-O notation and P vs NP. There’s also a Wikipedia page on time complexity. He attended Babai’s talk announcing the result in November 2015 and posted about it then, with a few updates since.)
Luckily, Babai has fixed the problem, so people with potentially isomorphic graphs they’d like to check in quasipolynomial time can rejoice once again.
I’ve been keeping up with graph isomorphism news by reading Erica Klarreich’s posts about it on the Quanta Magazine Abstractions blog. She explained the error Helfgott found on January 5th and posted an update on the fix nine days later. I am especially fond of her analogy for quasipolynomial time: “Very roughly speaking, his algorithm carries the graph isomorphism problem almost all the way across the gulf between the problems that can’t be solved efficiently and the ones that can — it’s now splashing around in the shallow water off the coast of the efficiently-solvable problems, whose running time is what computer scientists call ‘polynomial.’”
On Saturday, Helfgott gave a Bourbaki lecture on graph isomorphism. Francophones can watch it on Youtube. (Others can also watch it on Youtube but will understand less of it.) I’ll also be keeping an eye on the Gödel’s Lost Letter and P=NP blog. They’ve been covering Babai’s work on the graph isomorphism problem since he announced it, and if the weather cooperated, they just went to a conference where Babai gave a distinguished lecture on the topic.
Update, January 17, 2017: As he reports on his blog, Helfgott’s Bourbaki article is now on arXiv as well (in French).