{\huge A Big Result On Graph Isomorphism}

Theory works in mysterious ways \vspace{.5in}

László Babai is one of the world experts on complexity theory, especially related to groups and graphs.

Today we wish to discuss a new result that he has announced that will place graph isomorphism almost in polynomial time.

More exactly László shows that Graph Isomorphism is in Quasipolynomial Time: that is time of the form

$latex \displaystyle 2^{O(\log(n))^{c}}, &fg=000000$

Luca Trevisan already has made a post on this result, and Scott aaronson likewise. Luca further promises to be in Chicago next Tuesday when László gives his talk on the result---here is the abstract of the talk:

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 $latex {(\exp(\mathsf{polylog} \ n))}&fg=000000$ time.

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

He is following this up with a talk on Thursday the 12th at 4:30 in the Mathematics Department's Group Theory seminar titled, ``A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism Problem.''

Why Best Result In Years

Well for starters it is a vast improvement over the complexity of GI. And while we know nothing yet about the algorithm we can make some guesses about the result. These are just guesses, but may contribute to appreciating why the result is so important.

$latex {\bullet }&fg=000000$ The algorithm likely uses some interesting structural results about graphs and or groups. The latter connection is clear, but the former could be that the automorphism group of a graph plays an important role in GI. If these structure theorems indeed are there, they could easily help solve other problems that we have in complexity theory. David Rosenbaum, an expert on group isomorphism, raised this point to me: perhaps László's methods will finally move group isomorphism from quasi-polynomial into polynomial time.

$latex {\bullet}&fg=000000$ László in a 2013 paper with John Wilmes proved a quasi-polynomial time algorithm for isomorphism of structures called Steiner 2-designs that are more specialized. Not only that, they compute unique canonical forms and enumerate all the isomorphisms. A difference that makes the last thing possible, however, is that there can be at most quasi-poly many isomorphisms between Steiner 2-designs.

$latex {\bullet }&fg=000000$ In Luca's comment section it is raised whether or not László's new method uses the simple group classification. The famous classification result has had a myriad of applications in theory. Many are interested in removing the reliance on this extremely deep theorem: this is in spirit like our interest in de-randomizing algorithms.

$latex {\bullet }&fg=000000$ Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? It is also one of those problems that was in subexponential time and was not known to be in quasi-polynomial time.

$latex {\bullet}&fg=000000$ The word ``outline'' in László's talk abstract suggests that the proof is long, not surprising, and perhaps complicated, again not surprising. László is terrific so if he says he has the result, I will bet that all is okay. Two comments I just got are ``wow'' and ``Now it is down to factoring and short lattice vectors. Whew.''

Well, there are other intermediate problems besides these two and discrete log. Notably there is minimum circuit size, whose ``umbrella'' relation to GI and factoring and discrete log we covered earlier this year.

$latex {\bullet }&fg=000000$ Raising questions about other problems. This a surprising result. Is a similar result for factoring around the corner? Or shortest vectors? GI is also one of those problems that was in sub-exponential time and was not known to be in quasi-polynomial time. Placing factoring in this complexity class would be a huge difficulty for cryptography.

Open Problems

Is the result correct? What is the structure of the theorem? Does it give counting or canonical forms? And are there any new results that may be used elsewhere in theory?

Good luck to László; we all hope that the result is correct. What a major achievement.