Graph isomorphism

Posted on 05/11/2015 by Peter Cameron

I just read Ken Regan’s report on the Gödel’s Last Letter blog that Laci Babai has a quasi-polynomial algorithm for graph isomorphism

“Quasi-polynomial” means exp(O((log n)c)) for some c: c = 1 would be polynomial.

Congratulations Laci!

Oh, and here he is at my retirement bash:

Araujo, Babai, Cameron

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in Uncategorized and tagged , . Bookmark the permalink.

2 Responses to Graph isomorphism

  1. KWRegan says:
    05/11/2015 at 21:06

    Hello, Peter, and congratulations on your (active) retirement! I was just in London with Dick Lipton and also gave two talks at Oxford hosted by Joel Ouaknine. You might be amused to know that I heard the news from Dick just as I was leaving and fielded his initial draft of the post while on the Down train thanks to Great Western Rail’s wifi. We had dueling edits until I stitched things together as the train pulled into Paddington.

    Reply
  2. Peter Cameron says:
    06/11/2015 at 07:59

    Ken, I am sorry to have missed you, but I am coming to the end of two months in Portugal. Maybe our paths will cross one day …

    Reply

Leave a Reply

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

Gravatar
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 )

Cancel

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.