Monthly Archives: January 2017

Graph Isomorphism in Quasipolynomial time

Posted on 2017/01/17 by valuevar

My Bourbaki article on Babai’s algorithm for solving graph isomorphism in quasipolynomial time is now online. (Short story for those who have been following the matter in the last couple of weeks: Babai’s fix is both correct and elegant – … Continue reading →

Posted in Uncategorized | 7 Comments

Bourbaki talk

Posted on 2017/01/14 by valuevar

This afternoon – Saturday, 4pm, Paris time – I will give a Bourbaki talk on the work of Babai on the graph isomorphism problem, going as well over previous work (Luks, Weisfeiler- Le(h)man, etc.) that prepared the way towards it. … Continue reading →

Posted in Uncategorized | 1 Comment

Graph isomorphism in subexponential time

Posted on 2017/01/04 by valuevar

In the course of preparing my Bourbaki talk on Babai’s work on the graph isomorphism problem, I found an error. It is serious. Babai has succeeded in recovering a result that, while weaker, is still remarkable. Preparing a Bourbaki talk … Continue reading →

Posted in Uncategorized | Tagged , , , | 14 Comments