Wednesday, May 28, 2008

Gödel Prize

The ACM has just announced that Dan Spielman and Shang-Hua Teng will receive the Gödel prize at ICALP for their paper Smoothed Analysis of Algorithms: Why the Simplex Algorithm Usually Takes Polynomial Time.


  1. Congratulations to both of them!

  2. IMHO, Spielman and Teng deserve praise not only for their result, but also for the exceptional grace and clarity with which they wrote about it ... their article is a work of art.

    For which clarity and beauty, no doubt, their reviewers deserve praise too! :)

  3. In light of recent discussions about "conceptual" vs. "technical" work, it's good to see that this primarily conceptual work (not to belittle the technical details they had to work out) receive this prestigious award.

    Congratulations to the authors!

    On a tangential note, Lance - I am disappointed that you didn't have a prediction market going for the winner of Godel prize!