News for hackers. Stuff that matters.
Re:Graph Isomorphism Strikes Back by adrianN on Friday January 06, 2017 @05:22AM (#13335262)
Asymptotically fastest is unfortunately very different from fastest in practice. I mean salvage his ideas towards a quasipolynomial (or even polynomial!) algorithm for graph isomorphism. I don't really expect a practical algorithm for the problem in the near future.
Re:Graph Isomorphism Strikes Back by CJefferson on Friday January 06, 2017 @05:45AM (#13335373)
Graph isomorphism is interesting, in that practical algorithms already exist. It's actually very, very hard to produce difficult instances of the graph isomorphism problem (to be exact, instances where existing algorithms take non-polynomial time).

Much of the progress in recent years has come from first finding instances where existing algorithms (in particular, partitioning from Brendan McKay's Nauty) take exponential time, and understanding why.

Re:Graph Isomorphism Strikes Back by maverick_iceman on Friday January 06, 2017 @07:57AM (#13335899)
Reminds me of the Simplex algorithm.