3 ms·
Graph Isomorphism update
- cosenal 10y agoThis update is actually a big deal. The algorithm runs in subexponential time, but not quasipolynomial time after all.
- cvoss 10y agoThis 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 https://news.ycombinator.com/item?id=10553879 [2] https://news.ycombinator.com/item?id=10731022 https://news.ycombinator.com/item?id=10731022
- ertand 10y agoUpdate on the update: quasipolynomial claim restored http://people.cs.uchicago.edu/~laci/update.html http://people.cs.uchicago.edu/~laci/update.html