Favorite Theorems: Graph Isomorphism

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.