Sunday, August 26, 2012

Knuth Prize

Leonid Levin will receive the Knuth Prize, and give the corresponding lecture, at FOCS this year. The Knuth Prize is jointly given by ACM SIGACT and the IEEE TC-MFCS for outstanding contributions to theoretical computer science.

Levin easily deserves the award alone for his amazing two-page 1971 paper, actually two major research lines

Today we call the seminal NP-completeness result for Satisfiability the Cook-Levin theorem.

Levin did so much more, from the "right" definition for average-case hardness to (with Hastad, Impagliazzo and Luby) producing pseudorandom generators from any one-way function.

Congrats to Leonid!


  1. Congrats to Leonid!! Shame that no one else has congratulated him here.

  2. A lot congrats to Leonid:)

  3. People like Lenoid come from the scarcest Computational Resource...
    My congratulations to Lenoid!