For anyone who would like to know more about Laci Babai's talk yesterday on the graph isomorphism problem, it was livetweeted by Gabriel Gaster, who has done us unfortunates who don't live in Chicago a great service. Although obviously he couldn't tweet an entire proof, one can extract a surprisingly large amount of information (and better still, in a very short time) from his tweets about what the proof is like. In particular, it seems that the broad structure of the proof is a divide-and-conquer algorithm that deals with most graphs, but reduces the problem to looking at some particularly troublesome examples called Johnson graphs. But the latter can be understood sufficiently precisely that they can be dealt with algebraically (using the classification of finite simple groups). Also, while Babai's algorithm is a stunning theoretical advance, it won't be challenging the algorithms that are used in practice. Here the situation is similar to that with primality testing, where despite the existence of a polynomial-time deterministic algorithm, a randomized algorithm is more practical to use if you actually want to test whether a number is prime.
46 plus ones
Shared publicly•View activity
View 5 previous comments
- Terence Tao+15So, it seems that there is an inverse theorem powering the algorithm - one method for detecting GI that works for "random" graphs, an inverse theorem that roughly classifies all the "structured" graphs that fail to be resolved by that method, and a second method to take care of the structured cases?
I briefly touched at the edge of this problem when working on random graphs with Van Vu; we showed that asymptotically almost surely, their eigenvalues were disjoint, which reproved a previous result of Babai that GI was polynomial time for random graphs, as one could use the eigenvectors to locate the isomorphism. But we did not expect to have any structure theorem for the exceptional graphs that had repeated spectrum. Looks like Babai has found a much better criterion than repeated spectrum though to push the strategy through.
Am looking forward to reading a preprint...Nov 11, 2015
- good luck LB! on the edge of my seat like everyone else! continuing the close marriage of group theory and (T)CS that seems likely to continue for decades!Nov 12, 2015
- Following are notes by Jeremy Kun: http://jeremykun.com/2015/11/12/a-quasipolynomial-time-algorithm-for-graph-isomorphism-the-details/Nov 12, 2015
- Video of the talk by Babai on graph isomorphism: http://people.cs.uchicago.edu/~laci/2015-11-10talk.mp4Nov 17, 2015
- Oh my!
Have we reached a historic moment, not just in the sense that the result is fairly important, but that it was made so readily accessible to people in such a short time?
Nov 17, 2015
- from the great kun notes (thx PH) it sounds like johnson graphs play a big role & maybe are a/ the particular "hard" cases for GI...? am now wondering of interesting findings on them & connections to complexity theory etc...
https://en.wikipedia.org/wiki/Johnson_graphNov 17, 2015