3 ms·
Mathematicians Are Stunned by This Chicago Professor’s New Proof
- ColinWright 11y agoIt's true that this is a really, really big theoretical advance, but it has almost zero impact on P vs NP. It's been believed for a long time that graph isomorphism is "close to P" for some suitable definitions. And this story has been discussion here on HN many many times over the past few weeks. So this is a nice article about a seriously major breakthrough, but take all the P vs NP speculation with a huge handful of salt. ================ Discussions: https://news.ycombinator.com/item?id=10731022 https://news.ycombinator.com/item?id=10731022 (75 comments) Landmark Algorithm Breaks 30-Year Impasse (quantamagazine.org) https://news.ycombinator.com/item?id=10505231 https://news.ycombinator.com/item?id=10505231 (41 comments) Quasi-Polynomial Algorithm for Graph Isomorphism (scottaaronson.com) https://news.ycombinator.com/item?id=10553879 https://news.ycombinator.com/item?id=10553879 (33 comments) A Quasipolynomial Time Algorithm for Graph Isomorphism: The Details (jeremykun.com) https://news.ycombinator.com/item?id=10610361 https://news.ycombinator.com/item?id=10610361 (3 comments) A Little More on the Graph Isomorphism Algorithm (rjlipton.wordpress.com) ================ Here are some of the other submissions: https://news.ycombinator.com/item?id=10504883 https://news.ycombinator.com/item?id=10504883 Graph Isomorphism in Quasi Polynominal Time (calendar.google.com) https://news.ycombinator.com/item?id=10506476 https://news.ycombinator.com/item?id=10506476 Graph Isomorphism in Quasi-polynomial time (uchicago.edu) https://news.ycombinator.com/item?id=10508418 https://news.ycombinator.com/item?id=10508418 Laci Babai and Graph Isomorphism (lucatrevisan.wordpress.com) https://news.ycombinator.com/item?id=10512074 https://news.ycombinator.com/item?id=10512074 A Big Result On Graph Isomorphism (rjlipton.wordpress.com) https://news.ycombinator.com/item?id=10542464 https://news.ycombinator.com/item?id=10542464 The world's fastest isomorphism testing program (1993) (stonybrook.edu) https://news.ycombinator.com/item?id=10547501 https://news.ycombinator.com/item?id=10547501 Summary of Babai's Breakthrough on Graph Isomorphism (reddit.com) https://news.ycombinator.com/item?id=10547881 https://news.ycombinator.com/item?id=10547881 Babai's Breakthrough on Graph Isomorphism (reddit.com) https://news.ycombinator.com/item?id=10553139 https://news.ycombinator.com/item?id=10553139 New algorithm efficiently solves graph isomorphism problem (sciencenews.org) https://news.ycombinator.com/item?id=10553152 https://news.ycombinator.com/item?id=10553152 Graph Isomorphism in Quasipolynomial Time (uchicago.edu) https://news.ycombinator.com/item?id=10562857 https://news.ycombinator.com/item?id=10562857 Solution to graph isomorphism problem found, improves understanding of P and NP (sciencenews.org) https://news.ycombinator.com/item?id=10565125 https://news.ycombinator.com/item?id=10565125 Claimed breakthrough in graph isomorphism algorithm (technologyreview.com) https://news.ycombinator.com/item?id=10601316 https://news.ycombinator.com/item?id=10601316 Graph Isomorphism in Quasipolynomial Time I [video] (uchicago.edu) https://news.ycombinator.com/item?id=10634234 https://news.ycombinator.com/item?id=10634234 László Babai Claims Quasipolynomial Algorithm for Graph Isomorphism (aperiodical.com) https://news.ycombinator.com/item?id=10687741 https://news.ycombinator.com/item?id=10687741 Laszlo Babai's Talk on His Quasipolynomial Time Algorithm for Graph Isomorphism (uchicago.edu) https://news.ycombinator.com/item?id=10729128 https://news.ycombinator.com/item?id=10729128 Graph Isomorphism in Quasipolynomial Time (Babai's Preprint) (arxiv.org) https://news.ycombinator.com/item?id=10730670 https://news.ycombinator.com/item?id=10730670 Graph Isomorphism in Quasipolynomial Time (arxiv.org) https://news.ycombinator.com/item?id=10735861 https://news.ycombinator.com/item?id=10735861 Graph isomorphism is quasi-polynomial time by Laci Babai (arxiv.org) https://news.ycombinator.com/item?id=10737655 https://news.ycombinator.com/item?id=10737655 Algorithm Solves Graph Isomorphism in Record Time (quantamagazine.org) https://news.ycombinator.com/item?id=10786874 https://news.ycombinator.com/item?id=10786874 Graph Isomorphism in Quasipolynomial Time (arxiv.org)
- DrScump 11y agoThank you for spending so much time on this and other reference-cleanup and dupe-cleanup efforts; it can be a pretty thankless job in my experience.