https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-gr...
https://rjlipton.wordpress.com/2015/11/09/the-world-series-o...
https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomo...
I expect he will post more as he gets more information.
https://rjlipton.wordpress.com/2015/11/04/a-big-result-on-gr...
https://rjlipton.wordpress.com/2015/11/09/the-world-series-o...
https://rjlipton.wordpress.com/2015/11/11/a-fast-graph-isomo...
I expect he will post more as he gets more information.
If factoring is indeed in the quasi-polynomial class, the above may well be the understatement of the decade.
But all previously encrypted messages would effectively become plain text to anyone with the foresight to save them.
> But then again, in practice, graph isomorphism has already been “basically in P” for decades! If you have two large graphs for which you actually need to know whether they’re isomorphic, just download NAUTY and run it.
> This contrasts with the case of factoring, for which I’d personally say that it remains much less clear whether it should or shouldn’t be in P.