News for hackers. Stuff that matters.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by eximius on Wednesday November 04, 2015 @11:23AM (#10507606)
I know a guy who may have independently come up with the same or a similar result. He's been keeping it under wraps because he's not a mathematician and hasn't proved it, just come up with the method.

I've advised him to upload his results somewhere as soon as possible because he's been working on this for several years. I'll be very interested to see how their methods differ.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JadeNB on Wednesday November 04, 2015 @12:23PM (#10508047)
Giving false proofs that GI is in P or a related time class is, I think, a common occupation (see, for example, https://rjlipton.wordpress.com/2009/11/04/on-mathematical-di... ); so, if all you know is that this guy thinks he has a solution to the problem, and if the guy is not a mathematician and doesn't have a proof, then the balance of probabilities is that he's probably mistaken (but there's no harm in making the work publicly available, just in case).
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by eximius on Wednesday November 04, 2015 @09:29PM (#10511248)
I've seen the method and I have a background in math, just not enough to really help prove it.

I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least. Even if his solution isn't polynomial it might be quasi polynomial like this result, in which case the differences would be enlightening.

The most likely case is that my friends work is polynomial but wrong in some obscure way. But it will be interesting nonetheless.

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by JadeNB on Wednesday November 04, 2015 @09:56PM (#10511361)
> I was never claiming that he succeeded, just that he had something similar that worked in all our tests, at least.

It's hard to tell the running time of an algorithm by testing; an O(1) algorithm is indistinguishable from an O(2^(2^n)) algorithm if you only run them on inputs up to n = 10^(10^(10^(34))), say.

(That sounds facetious, and it kind of is, but it cuts the other way, too: I seem to remember that polynomial-time primality testing isn't used in practice because the constants are so huge that, on 'real-life' inputs, it's impractically worse than probabilistic testing.)

Re:Quasi-Polynomial Algorithm for Graph Isomorphism by 314 on Wednesday November 04, 2015 @01:07PM (#10508372)
Don't worry, we all have an idea for a method to solve GI in P tucked in the back of a drawer. Best to just let it go. Personally I know where I got stuck many years ago and I'm very excited to see somebody do it for real.
Re:Quasi-Polynomial Algorithm for Graph Isomorphism by eximius on Wednesday November 04, 2015 @09:26PM (#10511237)
Don't understand the downvotes guys... not cool.