7
$\begingroup$

Last year, Laszlo Babai proved that the graph isomorphism problem can be solved in time:

$$ \exp(O(\log^c n)) $$

where $n$ is the number of vertices.

What is the best bound we have for $c$? (The case $c = 1$ would correspond to a polynomial-time algorithm for graph isomorphism.)

$\endgroup$
  • 2
    $\begingroup$ C=1 would actually be linear. (Unless you are hiding a constant inside exp()?) Gerhard "Sometimes Dreams Of Linear Life" Paseman, 2016.03.28. $\endgroup$ – Gerhard Paseman Mar 28 '16 at 21:58
  • 1
    $\begingroup$ Yes, just allow me to move that big O inside the exp... $\endgroup$ – Adam P. Goucher Mar 28 '16 at 22:29
  • 2
    $\begingroup$ I may be misremembering, but I think I recall Babai saying something like his proof should give $c=7$, possibly after some optimizations. If not, in that general ballpark. $\endgroup$ – usul Mar 28 '16 at 22:58
  • 2
    $\begingroup$ Yeah, in his talk at CMU I vaguely remember him saying something like $c = 11$. $\endgroup$ – Ryan O'Donnell Mar 29 '16 at 0:09
4
$\begingroup$

Babai apparently retracted some parts of his proof, now he claims that he can do $O(\exp(n^c))$ for some small $c$ (say, $c=0.01$), but not all $c>0$. See http://people.cs.uchicago.edu/~laci/update.html

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Gerhard Paseman Jan 5 '17 at 5:32
  • 3
    $\begingroup$ 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()$). $\endgroup$ – Steven Stadnicki Jan 5 '17 at 6:17
  • 1
    $\begingroup$ Since then, Babai corrected the proof, the quasipolinomial claim holds again. $\endgroup$ – Péter Komjáth Jan 10 '17 at 6:01
  • 2
    $\begingroup$ Now claims quasipolynomial again: people.cs.uchicago.edu/~laci/update.html $\endgroup$ – Ian Agol Jan 10 '17 at 15:27
  • 1
    $\begingroup$ 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. $\endgroup$ – Peter Heinig Aug 23 '17 at 12:37

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.