Hacker News new | ask | show | jobs
by jgn 3843 days ago
Thanks for posting this. In the future, could you please add the algorithm to the title? This feels a couple steps removed from clickbait. No offense intended; it's just a suggestion.
4 comments

> Babai has declined to speak to the press, writing in an email: “The integrity of science requires that new results be subjected to thorough review by expert colleagues before the results are publicized in the media.”

Quoth the media ... Apparently unironically.

I'm okay with Quanta Magazine leaving out the irony; I can imagine the Engadgets and Buzzfeeds of the world would omit his response and draw their own wild conclusions regardless.
"Top 10 ways your graphs may be isomorphic. Results will surprise you!!"
"We would like to explain how; but the proof is too long to be tweeted within the 144 character limit!"
For the nearly all practical purposes, there already exist efficient algorithms for GI. This work is mostly of interest for theoretical matters because it shows that GI can be solved in quasi-poly time for _all_ graphs, whereas previous work still had exponential time worst-cases. Hence why there isn't really a concise algorithm that you'd want to implement.
It's not clickbait, it just requires reading the article for the full story.

I also recommend this blog post: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algor...