In a demonstration of impeccable taste, ACM bestowed this year’s Turing Award on Leslie Valiant, for several contributions, including the development of computational learning theory (the foundational theory of machine learning) and of a theory about the complexity of combinatorial counting problems.
It is also notable that the Knuth Prize maintains a perfect record at predicting future Turing awards for theory.
When I first read the title of this post, I thought you referred to Lazlo Babai 🙂
It is also notable that the Knuth Prize maintains a perfect record at predicting future Turing awards for theory.
I guess that it depends on how you define “theory”. The Knuth Prize did not predict the awards to Ed Clarke, Allen Emerson and Joseph Sifakis (2007) and to Amir Pnueli (1996). Anyway, IMHO, there is definitely more Turing-award material in the list of Knuth Prize recipients.
What I meant is, so far, those who have won the Knuth have also won the Turing award, in the order in which they won the former. I agree that there have been a number of theoreticians who have recently won the Turing award without first winning the Knuth, including Rivest, Shamir and Adleman. Maybe the moral is that the highest honor in computing is, in fact, the Knuth prize.
What I meant is, so far, those who have won the Knuth have also won the Turing award, in the order in which they won the former.
Indeed. May this trend continue for the good of TCS!