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.

### Like this:

Like Loading...

*Related*

Woah…

Super exciting! Is there an announcement for the Thursday talk?

Pingback: Shtetl-Optimized » Blog Archive » G. Phi. Fo. Fum.

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

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.

Cool, share the notes after the talk 🙂

This informative abstract of Babai’s talk last year http://toc.csail.mit.edu/node/485 nicely lists some of the recent developments on GI. Babai had to skip the GI part in his epic Knuth prize lecture at STOC’15, where there was also a paper (http://arxiv.org/abs/1510.02195) addressing the primitive coherent configurations challenge he mentions at the end of the abstract.

Will the talk be filmed and the video be posted ?

Pingback: A Big Result On Graph Isomorphism | Gödel's Lost Letter and P=NP

Pingback: Cold Off The Press! | On The Shoulders Of Windmills

Pingback: Theoretical CS Opportunities at Harvard | Windows On Theory

Pingback: TECNOLOGÍA » A Big Result On Graph Isomorphism

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?

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

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

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

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.

https://twitter.com/gabegaster

Thanks for the pointer.

Jeremy Kun was also nice enough to write up a quite detailed summary on his blog:

http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/

Pingback: A canonical labeling technique by Brendan McKay and isomorphism testing of deterministic finite automata | Gentzen translated

Pingback: Babai breakthru: graph isomorphism in quasipolynomial time | Turing Machine

Laci’s paper is on the arXive!!: http://arxiv.org/abs/1512.03547

Pingback: A Primer on Graph Isomorphism | TRIFORCE STUDIO

Pingback: G. Phi. Fo. Fum. | TRIFORCE STUDIO

Pingback: Meanwhile Over In Computer Science – Study Score Calc

Pingback: How can you show that 2 (adjacency) matrices are isomorphic? – Math Solution