The graph isomorphism (GI) problem is an extremely interesting problem for computer scientists and mathematicians alike, and it is one of those problems whose complexity status is still unresolved. To this end, in this paper, Babai presents a breakthrough result, claiming that GI and in fact some more general problems, namely, string isomorphism (SI) and coset intersection (CI), are solvable in quasi-polynomial time.

Following the seminal work of Luks [1], Babai tackles GI first by switching to SI and uses combinatorics and group theory quite heavily to solve the problem. In particular, Luks’s recursive divide-and-conquer algorithm for SI faces the problem of a giant representation of the ambient group, which is handled by Babai efficiently. Very briefly this is done, as Babai mentions in the abstract, by “the local certificates routine, which is based on a new group theoretic result, the unaffected stabilizers lemma, which allows us to construct global automorphisms out of local information.”

What is the significance of this result? Babai makes rather long concluding remarks that suggest possible implications. Clearly, from a practical point of view, nothing much is expected, but from the angle of a complexity theorist, this is certainly remarkable! For instance, the result certainly indicates that GI is not NP-complete because, if it is, then all problems in NP will also have quasi-polynomial time algorithms.

The paper is extremely technical and at times quite hard to read, which is perhaps a common trait of most STOC papers, and Babai’s bottom-up exposition did not make it any easier to follow. At least I would have benefited more if there had been a high-level description of the algorithm in the beginning as a motivation to read further.