This amazing result shows that the graph isomorphism problem can be solved in "quasi-polynomial time." I think that many people have suspected this to be the case, but until now has this been shown. It's possible that there are problems, but hopefully these can be found and resolved by the community. If it turns out to be the case, the algorithm will have a lot of impact in applied math, as graphs have practical uses in a huge number of domains. I'm psyched.



posted by qiy: 1063 days ago