Re:Algorithm Solves Graph Isomorphism in Record Time (2015)
by jmmcd on Friday May 24, 2019 @04:43PM
(#20005117)
Slightly off-topic, this article has one of the best expositions I've seen (the Arthur-Merlin stuff) of P, NP, NP-complete, witnesses, and the idea of "evidence" for what complexity class the problem is in.
[ Parent
| on HN ]
Re:Algorithm Solves Graph Isomorphism in Record Time (2015)
by dbchiem on Friday May 24, 2019 @11:27PM
(#20006931)
Absolutely, I think the author did a magnificent job!.
Reading the article, all the intricacies (P/NP, polynomial/exponential, blind test, graph coloring) are quite clear and easy to comprehend.
Here are some gentle articles on the zero-knowledge in case anyone is curious:
https://blog.cryptographyengineering.com/2014/11/27/zero-kno...
Re:Algorithm Solves Graph Isomorphism in Record Time (2015)
by mpoteat on Friday May 24, 2019 @05:39PM
(#20005527)
Unfortunately I found all of the story-like exposition infuriating: they never even say what the new conjectured lower bound is.
Re:Algorithm Solves Graph Isomorphism in Record Time (2015)
by nine_k on Friday May 24, 2019 @10:06PM
(#20006683)
Likely it's the lower bound (of something) that an important conjecture in the paper gives? That is, it's not some new kind of a lower bound, but a way to refer to it?
Re:Algorithm Solves Graph Isomorphism in Record Time (2015)
by evrydayhustling on Friday May 24, 2019 @10:33PM
(#20006760)
100% this. One of the cleanest descriptions of key insights and broader scientific landscape ("glide path" from quasipolynomial to P) I have seen. Erica, if you are seeing this, nice work and I'll be watching for more.