Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by gone35 on Wednesday November 04, 2015 @10:59AM
(#10507439)
What. A. Bombshell. Sorry for the low-content post; but it is no exaggeration to say that this "might be the theoretical computer science result of the decade". I'm dying to see how Babai managed to pull it off.
[ Parent
| on HN ]
Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by yk on Wednesday November 04, 2015 @02:48PM
(#10509096)
With the news of the EM drive today, probably he confused himself with unclear notation on line 57 of the proof. ( It would be cool if he pulled it off, but even highly respected scientists make mistakes, and a blog post based on the title of a seminar is nothing to get excited about.)
Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by davidamarquis on Wednesday November 04, 2015 @06:10PM
(#10510484)
Good mathematical work is rarely an all or nothing proposition. Many independent ideas are required and when the mathematician is very good it is rare that there will be many mistakes.
So even if there are issues with some aspect of the proof there is usually lots of interesting stuff that can be salvaged. The proof of Fermat's last theorem as originally given is an example. It was wrong, though it got patched later, but the original work was still very exciting I think.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by bmh100 on Wednesday November 04, 2015 @04:45PM
(#10510017)
Since you seem knowledgeable about this area, do you know a good algorithm for generating isomorphic forms of a given weighted acyclic directional graph? I would be looking to reduce nesting level and/or total edge count.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by gone35 on Thursday November 12, 2015 @12:22PM
(#10554518)
Sorry not my field! But I would first give NAUTY[1] a try before trying more exotic, structure-exploiting stuff.
[1] http://www3.cs.stonybrook.edu/~algorith/implement/nauty/impl...
Re:Quasi-Polynomial Algorithm for Graph Isomorphism
by fitzwatermellow on Wednesday November 04, 2015 @01:05PM
(#10508363)
Yes, it's a rarity indeed!