We start our favorite theorems of the last decade with a blockbuster improvement in a long-standing problem.
Graph Isomorphism in Quasipolynomial Time by László Babai
The graph isomorphism problem takes two graphs G and H both on n nodes and asks if there a permutation \(\sigma\) such that \((i,j)\) is an edge of G if and only if \((\sigma(i),\sigma(j))\) is an edge of H. While we can solve graph isomorphism in practice, until Babai's paper we had no known subexponential algorithm for the problem.
Graph Isomorphism has a long history in complexity. It has its own self-named complexity class in the zoo. It's one of the few decision problems in NP not known to be NP-complete or in P. Graph Isomorphism and its complement are the poster child problems for complexity classes AM, SZK and SPP, public-coin proof systems, and the minimum-size circuit problem. Köbler, Schöning and Torán wrote a whole book on the structural complexity of graph isomorphism.
Graph Isomorphism has the kind of group structure that suggests a quick quantum algorithm, but that remains an annoying open problem.
Babai found a simple algorithm and proof based on Johnson Graphs. Who am I kidding? You would need several months to work through the paper even for an expert group theorist.
Babai has been working on graph isomorphism since the 80's. In November 2015, he announced a talk with that title and the theory world went crazy. They needed a larger room. We invited Babai down to Georgia Tech to give a talk. A week before he sends me an email saying the proof no longer gave the quasipolynomial time bound and asks if he should still give the talk. We say of course and he gives the talk on January 9, 2017, describing the problem with the proof. And then he announces "It's been fixed". I witnessed history in the making.
I don't suppose you have any update on the publication status of this. These things can take a long time, I know, but it has been almost eight years since the (later found buggy and fixed) STOC paper.
ReplyDeleteDon't forget the evidence that the standard approach to such quantum algorithm is known not to work! Moore, Russell, and Sniady '06: https://arxiv.org/abs/quant-ph/0612089.
ReplyDeleteWasn't AM invented basically because we didn't know (and still don't know!) how to show GI is in coNP, but they could show it was in coAM? (Which is still enough to show that if GI is NP-complete then PH collapses.)
Also, I'm a big fan of the Köbler, Schöning, Torán book. You can teach maybe 1/2-3/4 of a course on computational complexity in general just from that book alone.