Update on Babai’s result

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.

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , , . Bookmark the permalink.

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 )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.