# Laci Babai and Graph Isomorphism

Next Tuesday, a week from today, Laci Babai will talk at the University of Chicago about a new algorithm that solves graph isomorphism in quasipolynomial time. There should also be a follow-up talk the following Thursday that, by a lucky coincidence, I will be able to attend, and then report back.

Meanwhile, if you have any gossip on the proof, then, by any means, go ahead and share it in the comments.

## 25 thoughts on “Laci Babai and Graph Isomorphism”

1. Woah…

2. I wonder if the analysis of the algorithm relies on the classification of finite simple groups.

3. I don’t have any insider info, so this is purely speculation, but he did publish a very interesting paper in ITCS 2014 on structure of automorphism groups of strongly regular graphs, that did not have an immediate algorithmic application but would indeed be a very important step on the way to a quasipolynomial time algorithm for strongly regular graphs.

Since the previously best-known GI algorithm is based on the polynomial time algorithm for bounded-degree graphs, which in turn is based on the structure of automorphism groups of bounded-degree graphs, it’s extremely plausible that his ITCS paper has been leveraged into a quasipolynomial time algorithm that works in a divide-and-conquer fashion based on this structure theorem…but even assuming that is the case, there is still the mystery of how a structure theorem about _strongly regular_ graphs is somehow applied to the general case; isomorphism testing of strongly regular graphs is/was not known to be GI-complete, and that by itself would have been a major result!

And indeed, his ITCS paper did depend on the classification of finite simple groups.

4. Is it expected that the algorithm produces an isomorphism in that time (in the case the graphs are isomorphic), or just that it answers yes/no to the isomorphism question in quasipoly time?

5. The problem is self-reducible in such a way that an algorithm that answers the yes/no question can be converted, with polynomial slow-down, to an algorithm that outputs an isomorphism if one exists

6. In addition, I suspect that this algorithm works by actually producing a canonical form for each graph.

7. Any news from the talk? I’ve been waiting impatiently for today and now can’t find anything online about how it went.

8. On Twitter @gabegaster was live-tweeting through the talk and described some of the essential parts. I think the impressive take-home message is that the algorithm seems actually quite a bit simpler than I would have thought, or else possibly it was just presented so brilliantly as to appear simple.