Graph isomorphism

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

Advertisements

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:

    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.

  2. 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 …

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