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 – and I spent last week going through other things to make sure that the overall procedure was correct as well. I gave a Bourbaki talk on all of this last Saturday; here is the video.)
Bourbaki talks, and the articles that accompany them, are expository. As many readers know, they are given by invitation; speakers are designated by N. Bourbaki (who does not exist) and assigned to work on a recent paper, or series of papers, by other people. The topic is typically close to one of the speaker’s specialties, but not quite within it.
A Bourbaki article has a target audience broader than that of specialists, though of course it is still aimed at people in maths and allied fields. It is often a step in the process by which a new proof is elucidated, polished, and in general assimilated into the general body of knowledge. I have tried to do my best for Babai’s remarkable work.
I also hope this will help lead to further improvements in the area, now that the correctness and precise strength of the result are clearer.
Thank you for doing this! Is there any chance that a translation will appear in English?
One of my postdocs floated the idea of translating this into English. I’ll talk to him again about it.
Any update? Will the student do it?
The translation is done: https://arxiv.org/abs/1710.04574
Pingback: Laci Babai Visits Israel! | Combinatorics and more
Reblogged this on Sublime Illusions.
Pingback: Babai’s Updated Results | Sublime Illusions