Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by jgn on Tuesday December 15, 2015 @01:21PM
(#10739406)
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.
[ Parent
| on HN ]
Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by tragic on Tuesday December 15, 2015 @01:25PM
(#10739436)
> 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.
Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by grrowl on Wednesday December 16, 2015 @08:34PM
(#10748869)
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.
Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by kzhahou on Tuesday December 15, 2015 @04:21PM
(#10740574)
"Top 10 ways your graphs may be isomorphic. Results will surprise you!!"
Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by williamjennings on Tuesday December 15, 2015 @09:15PM
(#10741915)
"We would like to explain how; but the proof is too long to be tweeted within the 144 character limit!"
Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by riscy on Tuesday December 15, 2015 @03:02PM
(#10740074)
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.
Re:Graph Isomorphism Algorithm Breaks 30-Year Impasse
by kzrdude on Tuesday December 15, 2015 @03:02PM
(#10740073)
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...