Timeline for Complexity of graph isomorphism
Current License: CC BY-SA 3.0
6 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Aug 23, 2017 at 12:37 | comment | added | Peter Heinig | It seems useful to point out Aleksandar Makelov: Graph Isomorphism in quasipolynomial time. Part III Essay. Cambridge. 2015. This is the only independent exposition currently known to me. Makelov's nice essay is in particular very careful and explicit about its own mode of organizing the material. This mention does not express any opinion of mine about the correctness of either about Babai's proof or Makelov's work. | |
| Jan 10, 2017 at 15:27 | comment | added | Ian Agol | Now claims quasipolynomial again: people.cs.uchicago.edu/~laci/update.html | |
| Jan 10, 2017 at 6:01 | comment | added | Péter Komjáth | Since then, Babai corrected the proof, the quasipolinomial claim holds again. | |
| Jan 5, 2017 at 6:17 | comment | added | Steven Stadnicki | Actually, he can do $O(\mathrm{exp}(n^c))$ for all $c$; his claim is $\mathrm{exp}(\mathrm{exp}(O(\sqrt{\log n})))$ (modulo some polylog factors in the $O()$). | |
| Jan 5, 2017 at 5:32 | comment | added | Gerhard Paseman | It would be more clear to say that the claim of quasi polynomial time is retracted. This may affect the proofs of the runtime analysis, but the core results are unchanged, if I read the announcement correctly. Gerhard "Core Theory Is Important Too" Paseman, 2017.01.04. | |
| Jan 5, 2017 at 5:00 | history | answered | Péter Komjáth | CC BY-SA 3.0 |