Babai’s Result: Still a Breakthrough
Even after today’s retraction of quasi-polynomial time for graph isomorphism
|Cropped from source|
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. Update 1/10: He has posted a 1/9 update reinstating the claim of quasi-polynomial time with a revised algorithm. As we’ve noted, he is currently speaking at Georgia Tech, and we hope to have more information soon.
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.
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 for some constant . 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.
He also chose to give a series of talks on his result. Some details of the talks were reported by Jeremy Kun here.
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’s 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—and we hope it takes less time.
In particular, his algorithm still runs faster than for any you care to name. For comparison, for more than three decades before this paper, the best worst-case time bound was essentially due to Eugene Luks in 1983. The new bound in full is
for some fixed that will emerge in the revised proof.
The important term is the . The function is exponential in . We previously encountered a recursion involving 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 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 given by formulas built using the operations and and . Assign each formula a level by the following rules:
- The identity function has level .
- If has level and has level then and have level .
- If has level then has level .
- If has level then has level .
Note that if has level then so does the power for any fixed because . The functions of level include not only all the polynomials but also all quasi-polynomial functions and ones such as , which is higher than quasi-polynomial when .
The amended bound on GI, however, belongs to level , 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 that are sufficiently well behaved:
- If and all but one of have well-defined levels , , and/or , respectively, then the other level is well-defined and satisfies .
Rule 5 subsumes rules 3 and 4 given that has level and has level . A special case is that when and has level , then has level .
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 , , , and so on all have the same level. It enables defining functions of intermediate levels where .
Can the GI algorithm be improved to a level ?
We note one prominent instance of level 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 for the discrete logarithm problem.
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.
[fixed discussion of terms related to , added to the intro an update about the claim being reinstated]