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

• An independent discovery of NP-completeness and
• Universal search

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!