# Complexity of graph isomorphism

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

• C=1 would actually be linear. (Unless you are hiding a constant inside exp()?) Gerhard "Sometimes Dreams Of Linear Life" Paseman, 2016.03.28. – Gerhard Paseman Mar 28 '16 at 21:58
• Yes, just allow me to move that big O inside the exp... – Adam P. Goucher Mar 28 '16 at 22:29
• 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. – usul Mar 28 '16 at 22:58
• Yeah, in his talk at CMU I vaguely remember him saying something like $c = 11$. – Ryan O'Donnell Mar 29 '16 at 0:09

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
• 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()$). – Steven Stadnicki Jan 5 '17 at 6:17