Laszlo Babai has claimed an astounding theorem, that the Graph Isomorphism problem can be solved in quasipolynomial time. On Tuesday I was at Babai’s talk on this topic (he has yet to release a preprint), and I’ve compiled my notes here. As in Babai’s talk, familiarity with basic group theory and graph theory is assumed, and if you’re a casual (i.e., math-phobic) reader looking to understand what the fuss is all about, this is probably not the right post for you. This post is research level theoretical computer science. We’re here for the juicy, glorious details.
Note: this blog post will receive periodic updates as my understanding of the details improve.
Background on Graph Isomorphism
I’ll start by giving a bit of background into why Graph Isomorphism (hereafter, GI)…
View original post 4,102 more words