{\huge Babai's Result: Still A Breakthrough}
Babai made a retraction today \vspace{.15in}
László Babai is famous for many things, and has made many seminal contributions to complexity theory. Last year he claimed that Graph Isomorphism (GI) is in quasi-polynomial time.
Today Laci posted a retraction of this claim, conceding that the proof has a flaw in the timing analysis, and Ken and I want to make a comment on what is up.
Laci credits Harald Helfgott with finding the bug after ``spending months studying the paper in full detail.'' Helfgott's effort and those by some others have also confirmed the mechanism of Laci's algorithm and the group-theoretic analysis involved. Only the runtime analysis was wrong.
Helfgott is a number theorist whose 2003 thesis at Princeton was supervised by Henry Iwaniec with input by Peter Sarnak. Two years ago we discussed his claimed proof of the Weak Goldbach Conjecture, which is now widely accepted.
The Claim
In December 2015, Laci posted to ArXiv an 89-page paper whose title claimed that GI can be solved in quasi-polynomial time. Recall that means that the algorithm runs in time $latex {n^{(\log n)^{c}}}&fg=000000$ for some constant $latex {c \ge 1}&fg=000000$. This an important time bound that is above polynomial time, but seems to be the right time bound for many problems. For example, group isomorphism has long been known to be in quasi polynomial time. But the case of graphs is much more complex, and this was reason that Babai's claimed result was so exciting. We covered it here and here plus a followup about string isomorphism problems that were employed.
Babai also choose to give a series of talks on his result. Some details of the talks were reported by Jeremy Kun here.
\includegraphics[width=3in]{BabaiTalk.jpg}
The Amendment
Retracting a claim is one of the hardest things that any researcher can do. It is especially hard to say when to stop looking for a quick-fix and make an announcement. It may not help Laci feel any better, but we note that Andrew Wiles' original proof of Fermat's Last Theorem was also incorrect and took 15 months to fix. With help from Richard Taylor he repaired his proof and all is well. We wish Laci the same outcome---although we hope it takes less time.
In particular, his algorithm still runs faster than $latex {\exp(n^{\epsilon})}&fg=000000$ for any $latex {\epsilon > 0}&fg=000000$ you care to name. For comparison, for more than three decades before this paper, the best worst-case time bound was essentially $latex {\exp(n^{0.5})}&fg=000000$ due to Eugene Luks in 1983. The new bound in full is
$latex \displaystyle B(n) = e^{e^{(\log\log n)^c \sqrt{\log n}}} &fg=000000$
for some fixed $latex {c > 0}&fg=000000$ that will emerge in the revised proof.The important term is the $latex {\sqrt{\log n}}&fg=000000$. The function $latex {e^{\sqrt{\log n}}}&fg=000000$ is exponential in $latex {n^{o(1)}}&fg=000000$. We previously encountered $latex {e^{\sqrt{\log n}}}&fg=000000$ in the running time of space-conserving algorithms for undirected graph connectivity (see this paper) before Omer Reingold broke through by getting the space down to $latex {\log n}&fg=000000$ and (hence) the time down to polynomial. So there is some precedent for improving it.
Some Intermediate Thoughts
As things stand, however, GI remains in the ``extended neighborhood'' of exponential time. Here is how to define that concept: Consider numerical functions $latex {f(x)}&fg=000000$ given by formulas built using the operations $latex {+,*}&fg=000000$ and $latex {\exp}&fg=000000$ and $latex {\log}&fg=000000$. Assign each formula a level by the following rules:
Note that if $latex {f}&fg=000000$ has level $latex {k}&fg=000000$ then so does the power $latex {f^c}&fg=000000$ for any fixed $latex {c > 0}&fg=000000$ because $latex {f^c = \exp(c\log f)}&fg=000000$. The functions of level $latex {0}&fg=000000$ include not only all the polynomials but also all quasi-polynomial functions and ones such as $latex {\exp(\exp((\log\log n)^c))}&fg=000000$, which is higher than quasi-polynomial when $latex {c > 1}&fg=000000$.
The amended bound on GI, however, belongs to level $latex {1}&fg=000000$, which is what we mean by its staying in the extended neighborhood of exponential time. This is the limit on regarding the amended algorithm as ``sub-exponential.''
It also makes us wonder about why it is so difficult to find natural problems with intermediate running times. We can define this notion by expanding the notion of ``level'' with a new rule for functions $latex {f,g,h}&fg=000000$ that are sufficiently well behaved:
This subsumes rules 3 and 4 given that $latex {\exp(\cdot)}&fg=000000$ has level 1 and $latex {\log(\cdot)}&fg=000000$ has level $latex {-1}&fg=000000$. We wonder when and where rule 5 might break down, but we note that careful application of rule 2 for multiplication when expanding a power makes it survive the fact that $latex {\exp(g(x)}&fg=000000$, $latex {(\log x)^{g(x)}}&fg=000000$, $latex {(\log\log x)^{g(x)}}&fg=000000$, and so on all have the same level. It enables defining functions of intermediate levels $latex {\ell}&fg=000000$ where $latex {0 < \ell < 1}&fg=000000$.
Can the GI algorithm be improved to a level $latex {\ell < 1}&fg=000000$?
We note one prominent instance of level $latex {1/2}&fg=000000$ in lower bounds: Alexander Razborov and Steven Rudich proved unconditionally in their famous ``Natural Proofs'' paper that no natural proof can show a level higher than $latex {1/2}&fg=000000$ for the discrete logarithm problem.
Open Problems
The obvious open problems are dual. Is the amended result fully correct? And can the original quasi polynomial time be restored in the near future, or at least some intermediate level achieved? We hope so.