Landmark Algorithm for Graph Isomorphism

[jedishrfu]

Quanta Magazine published this article on a potentially new algorithm for graph isomorphism by Prof Laszlo Babai of the University of Chicago:

https://www.quantamagazine.org/20151214-graph-isomorphism-algorithm/

There's a reference to the Arxiv preprint here:

http://arxiv.org/abs/1512.03547v1

 

[Borg]

A fascinating article jedishrfu. Thanks for sharing that.

 

[Fooality]

Super exciting. I always sensed the graph isomorpism problem has never belonged with the others, but when you sit down and try to come up with with an algorithm to prove it, (as I have) it's elusive. I hope this pans out, because pinning down exactly what makes it different could reveal a bunch of other problems that also have solutions in the "metropolitan area of P" previously thought not to.

 

[WWGD]

No surprise it was a Hungarian, a lot of great Graph Theorists and Combinatorialists (and general Mathematicians) from Hungary.