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.)

Improve this question
$\endgroup$
4
  • 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
    Commented Mar 28, 2016 at 21:58
  • 1
    $\begingroup$ Yes, just allow me to move that big O inside the exp... $\endgroup$
    – Adam P. Goucher
    Commented Mar 28, 2016 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
    Commented Mar 28, 2016 at 22:58
  • 2
    $\begingroup$ Yeah, in his talk at CMU I vaguely remember him saying something like $c = 11$. $\endgroup$
    – Ryan O'Donnell
    Commented Mar 29, 2016 at 0:09

1 Answer 1

Reset to default
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

Improve this answer
$\endgroup$
5
  • $\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
    Commented Jan 5, 2017 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
    Commented Jan 5, 2017 at 6:17
  • 1
    $\begingroup$ Since then, Babai corrected the proof, the quasipolinomial claim holds again. $\endgroup$
    – Péter Komjáth
    Commented Jan 10, 2017 at 6:01
  • 2
    $\begingroup$ Now claims quasipolynomial again: people.cs.uchicago.edu/~laci/update.html $\endgroup$
    – Ian Agol
    Commented Jan 10, 2017 at 15:27
  • 2
    $\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
    Commented Aug 23, 2017 at 12:37

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .