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.
in theory 
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.
Thanks for the pointer.
Jeremy Kun was also nice enough to write up a quite detailed summary on his blog:
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