12 comments on original post
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.
Add a comment...