An algorithm has just been proposed for solving the graph isomorphism problem in quasipolynomial time, dealing a serious blow to hard problems all over the world. But let me first explain what all of those words mean.
Graphs, you’ll recall, are simply collections of nodes linked together by edges. If you look at the image below, you see three different graphs. Each has four nodes linked together with four edges. But wait, are they actually different? If you take the graph to the far left and twist the top and bottom, you get the graph in the middle. So we say these two graphs are the same, or in mathematical jargon: isomorphic. Any time you can twist and deform to get from one picture to another (without detaching any of the edges or nodes), you are dealing with isomorphic graphs. So what about the graph on the far right, can you twist and pull that one to make it look like the first two?
Sure, you can. This is the essence of the graph isomorphism problem: how do we decide when two graphs are isomorphic? And this example above is pretty easy, but as you increase the number of nodes, this quickly becomes a really hard problem. In the parlance of algorithms, it is even thought to be NP hard. Or rather, it was thought to be NP hard until University of Chicago’s Laszlo Babai totally pwned it last week. It was announced that Babai has discovered a quasipolynomial time algorithm for deciding isomorphism of graphs, which is a massive discovery in the face of classicaly super-duper hard problems in complexity theory.
When we measure the speed of this sort of algorithm, we measure it relative to the number of nodes n. A really fast algorithm would only increase in complexity at the rate of a polynomial in n. A really slow algorithm would increase exponentially relative to n. Babai’s algorithm seems to sit somewhere between the two. It’s faster than anything that’s ever been done before, bit it’s not quite polynomial fast either, so fittingly, it is called quasi-polynomial.
Babai is unveiling his results in a series of three talks at the University of Chicago, the first two of which have already been graciously livetweeted by Gabriel Gaster — a sincere tip of the hat to Gaster for this exciting blow-by-blow.
Screenshot from Gabe Gaster’s Livetweet of Babai’s first Graph Isomorphism Talk.
Computer scientist and blogger at Shtetl-Optimized, Scott Aaronson, gives a nice breakdown of the striking features of this new result that make it such a dramatic step forward from its predecessors, including its relationship to string isomorphisms, finite simple groups, and Luks’ algorithm from 1982. For all the gory details on the mathematical content of Babai’s talk, Jeremy Kun posted a recap of the November 12th lecture, which he intends to update as further details emerge. In the meantime, there are some thoughtful discussions going on over in the comments section at In Theory, computer scientist Luca Trevisan’s blog.
As for the preprint, rumor has it that Babai said it will be available “soon, soon.” It’s all very exciting, but we have to remember to keep our proverbial hats on until everything is checked out. But it occurs to me that it suddenly became a lot more difficult to walk around glibly saying how hard it is to factor large numbers, and how secure our cryptosystems are because of that. Because who knows, graph isomorphism today…maybe factoring tomorrow?
The graph isomorphism problem was not thought to be NP-hard. Babai showed subexponential bounds for graph isomorphism in 1983. Graph isomorphism is interesting because it’s one of the more famous NP-intermediate problems.
Thanks Jeff, after some thoughtful discussion with my complexity theory inclined colleagues, it turns out I wasn’t quite getting the subtlety. But it still holds that this is a paradigm shifting result. Thanks for reading!