Speaking of the complexity conference, my former PhD student Dieter van Melkebeek will receive the ACM SIGACT Distinguished Service award for his leadership in taking the conference independent. They grow up so fast!
Robin Moser and Gábor Tardos will receive the Gödel Prize for their work giving a constructive proof of the Lovász Local Lemma, one of my truly favorite theorems as it gave a far stronger bound, a shockingly simple and efficient algorithm and an incredibly beautiful proof. Back in 2009 Moser gave my all-time favorite STOC talk on an early version of the paper. I (and others) sat amazed as his algorithm and proof came alive. During the talk I asked Eric Allender sitting next to me "Are we really seeing a Kolmogorov complexity proof of the Lovász Local Lemma?" Yes, we did.
Cynthia Dwork will receive the Knuth prize given for her life's work. The prize would be justified by her work on distributed computing alone but it is her leadership in formalizing Differential Privacy, one of the coolest concepts to come out of the theoretical computer science community this century, that will leave her mark in theory history.
Congratulations to Dieter!
ReplyDeleteHis service for the TCS community during the years (SICOMP, Dagstuhl, etc.) is great. I most like his precision.