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 – 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.
Advertisements

About valuevar

I am a number theorist with side interests in combinatorics and group theory.
This entry was posted in Uncategorized. Bookmark the permalink.

6 Responses to Graph Isomorphism in Quasipolynomial time

  1. Huck Bennett says:

    Thank you for doing this! Is there any chance that a translation will appear in English?

  2. Pingback: Laci Babai Visits Israel! | Combinatorics and more

  3. Pingback: Babai’s Updated Results | Sublime Illusions

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s