I learned yesterday that Harald Helfgott had found a mistake in László Babai’s result on the complexity of graph isomorphism. The algorithm and the bulk of the analysis still stands; it was just problem with the accounting showing that the algorithm runs in quasipolynomial time.
Now Babai claims that the problem has been fixed and a replacement paper for the arXiv is in preparation. See here.
This is a case of the mathematics and computer science community functioning in the best possible way. The result is important enough to get careful scrutiny, and in this way any bugs are caught and fixed.
There is some information about this on the “Gödel’s Last Letter” blog, which you can find on the sidebar.
Advertisements
