Graph Isomorphism update

This update is actually a big deal. The algorithm runs in subexponential time, but not quasipolynomial time after all.

Update on the update: quasipolynomial claim restored

http://people.cs.uchicago.edu/~laci/update.html

This work was heralded all over the internet when it came out. Here's some great HN discussions: [1] on a blog post by Jeremy Kun, and [2] on a Quanta Magazine article. Kun has already updated his post to reflect the retracted claim.

A little disappointing that it's not quasipolynomial, but subexponential is still a great achievement! It means, as Babai says, the asymptotic complexity is better than e^(n^epsilon)) for any epsilon > 0. Have a look at the graph of e^(n^0.01) for huge n to get an idea of what this is like.

[1] https://news.ycombinator.com/item?id=10553879

[2] https://news.ycombinator.com/item?id=10731022