Laszlo Babai (University of Chicago): Graph Isomorphism in Quasipolynomial Time (Combinatorics and TCS seminar)

We outline an algorithm that solves the Graph Isomorphism (GI) problem and the related problems of String Isomorphism (SI) and Coset Intersection (CI) in quasipolynomial (exp(polylog n)) time.

The best previous bound for GI was \exp(\sqrt{n log n}), where n is the number of vertices (Luks, 1983). For SI and CI the best previous bound was similar, \exp(\sqrt{n}(log n)^c), where n is the size of the permutation domain (the speaker, 1983).

G. Phi. Fo. Fum. by Scott Aaronson

Earlier today, I was tipped off to what might be the theoretical computer science result of the decade. My source asked me not to break the news on this blog—but since other theory bloggers (and twitterers) are now covering the story, I guess the graph is out of the Babai.

According to the University of Chicago’s theory seminar calendar, on Tuesday of next week (November 10), the legendary Laszlo Babai will be giving a talk about a new algorithm that solves the graph isomorphism problem in quasipolynomial time. The previous fastest algorithm to decide whether two n-vertex graphs G and H are isomorphic—by Babai and Luks, back in 1983—ran in exp(√(n log n)) time. If we credit the announcement, Babai has now gotten that down to exp(polylog(n)), putting one of the central problems of computer science “just barely above P.” (For years, I’ve answered questions on this blog about the status of graph isomorphism—would I bet that it’s in BQP? in coNP? etc.—by saying that, as far as I and many others are concerned, it might as well just be in P. Of course I’m happy to reaffirm that conjecture tonight.)