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:
Advertisements
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.
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 …