László Babai in Chicago. Photo by Gabe Gaster, used with permission.

We’ve been slow to cover this, but if this week has taught us anything, it’s that taking your time over Important Maths News is always a good idea.

A couple of weeks ago, rumours started circulating around the cooler parts of the internet that László “Laci” Babai had come up with an algorithm to decide if two graphs are isomorphic in quasipolynomial time. A trio of mathematicians including Tim Gowers were on BBC Radio 4’s In Our Time discussing P vs NP while these rumours were circulating and made a big impression on Melvyn Bragg as they talked so excitedly about the prospect of something big being announced.

If Babai had done what the rumours were saying, this would be a huge advance – graph isomorphism is known to be an NP problem, so each step closer to a polynomial-time algorithm raises the P=NP excite-o-meter another notch.

And it looks like he’s done it! Babai presented the first part of his work in a seminar at the University of Chicago on the 10th of November. Gabe Gaster, who attended the talk, live-tweeted it. You can relive the excitement with a Storify of the whole thing. Is this the first live-tweeting of a groundbreaking mathematical advance?

Answering the Graph isomorphism pic.twitter.com/7VaX06oPH9

— Gabriel Gaster (@gabegaster) November 10, 2015

Babai has also put the video of his talk on his homepage. It’s 100 minutes long, and if you want to skip to the bit where the audience breaks into the restrained applause that Hollywood will re-enact as a standing ovation ending in Babai being carried out of the building by his peers, it’s at 1:34:45.

So, how did he do it? Lots of finite group theory. Jeremy Kun has written a very good blog post explaining the broad outline of the proof. I’ll nab this theorem statement from Jeremy:

Theorem: There is a deterministic algorithm for GI which runs in time $2^{O(\log^c(n))}$ for some constant $c$.

I won’t pretend I’ve read even Jeremy’s summary in detail (I’ve got a dog and a wife to feed tonight) but I enjoy the term “split-or-Johnson routine” purely because it could easily be a Nicholas brothers dance. László has given one more talk and is scheduled to do another, titled “A little group theory goes a long way: the group theory behind recent progress on the Graph Isomorphism problem” and “Graph Isomorphism in Quasipolynomial Time II: The ‘Split-or-Johnson routine'”. I don’t think anyone has live-tweeted those though, so we’ll have to wait until the full solution appears in writing to find out all the nitty-gritty.

We also have to wait to find out if Babai is even right – as his homepage says, none of this has been peer-reviewed yet! But for now, we’ve got a lot of new ideas that definitely represent a big breakthrough.