$\newcommand{\polylog}{\mathrm{polylog}}$ $\newcommand{\wto}{\widetilde{O}}$

January 9, 2017 update: quasipolynomial claim restored

On January 4 I announced that Harald Helfgott pointed out an error in the analysis of my Graph Isomorphism test. The error invalidated my previous claim of quasipolynomial efficiency. The text of the announcement is appended below.

On January 7 I discovered a replacement for the recursive call in the "Split-or-Johnson" routine that had caused the problem. With this modification, I claim that the Graph Isomorphism test runs in quasipolynomial time (now really).

The replacement consists of a few lines of pseudocode, analyzed via a simple new lemma on the structure of coherent configurations.

I am working on an updated arXiv posting.

Added on Jan 14, 2017. Click here for a description of the fix (the updated recursive call).


January 4, 2017 posting: quasipolynomial claim withdrawn

In December 2015 I posted a manuscript titled Graph Isomorphism in Quasipolynomial Time (arXiv:1512.03547) (v1:11 Dec 2015, v2:19 January 2016). The title states the claimed result.

A revised analysis of the (slightly1 modified) algorithm shows that it runs in subexponential but not quasipolynomial time. "Subexponential time" means it is faster than $\exp(n^{\epsilon})$ for every positive constant $\epsilon$. The specific running time is $\exp\exp(\wto(\sqrt{\log n}))$ where the $\wto$ notation implies a factor of $(\log\log n)^c$.

In particular, the algorithm still runs faster than say $\exp(n^{0.01})$. For comparison, for more than three decades before this paper, the best worst-case time bound was essentially $\exp(n^{0.5})$ (Luks, 1983). With this announcement, I am retracting the quasipolynomial claim. On the other hand, I affirm that significant progress has been made.

The technical content of the paper remains virtually unchanged. The previous analysis breaks down for one of the recursive steps of the combinatorial "Split-or-Johnson" procedure; but the "Split-or-Johnson" theorem remains valid with the updated timing analysis. All other results are unaffected. I am working on an updated arXiv posting (with a different title) that will also improve the presentation, following comments from several colleagues.

I wish to thank Harald Helfgott (University of Göttingen and CNRS) for spotting this error and for spending months studying the paper2 in full detail. Helfgott will publish his exposition of the algorithm (with the revised analysis) in the Bourbaki Seminar series.

Thanks to Harald's efforts and his unfailing attention to the most seemingly minute detail, I am now confident that the result, with the revised analysis, stands. Moreover, the new techniques introduced in the paper provide a framework and tools for further progress.

I apologize to those who were drawn to my lectures on this subject solely because of the quasipolynomial claim, prematurely magnified on the internet in spite of my disclaimers. I believe those looking for an interesting combination of group theory, combinatorics, and algorithms need not feel disappointed.


1 I was asked to clarify the nature of the "slight modification" of the algorithm. Upon learning about the mistake in the analysis, I rebalanced the value of one of the threshold parameters in the algorithm to optimize for the revised analysis. [↩]

2 Further information can be found on Helfgott's blog. [↩]

Footnotes added Jan 5, 2017.