Monthly Archives: January 2017

Graph Isomorphism in Quasipolynomial time

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 | 6 Comments

Bourbaki talk

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

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