4 ms·
Do you have a reference for that paper about graph isomorphism, please?
by Chris_Newton 10y ago
Do you have a reference for that paper about graph isomorphism, please?
- OJFord 10y agoI believe the parent commenter is probably referring to Laszlo Babai's late-2015 paper on quasipoly GI: https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/ https://jeremykun.com/2015/11/12/a-quasipolynomial-time-algo...
- openasocket 10y agohttps://arxiv.org/abs/1512.03547 https://arxiv.org/abs/1512.03547 Note it was actually Quasipolynomial time, not true polynomial time. It's also a pretty recent paper, so it could turn out to have flaws.
- JadeNB 10y ago> It's also a pretty recent paper, so it could turn out to have flaws. On the other hand, it's Babai, so it doesn't. :-)