Computational Complexity and other fun stuff in math and computer science from Lance Fortnow and Bill Gasarch
Tuesday, April 15, 2003
The ACM doctoral dissertation award, given to the best doctoral thesis in computer science,
was awarded to Venkatesan Guruswami for
his thesis "List-Decoding on Error-Correcting Codes". Another theorist, Tim Roughgarden, was one of the runners-up. This was definitely a great
year for theory Ph.D. theses.
Rumors are flying that theorists Ron Rivest, Adi Shami and Len Adleman won the Turing Award for their
work on the RSA cryptosystem. The Turing Award is the highest honor in computer science, the closest we have to a Nobel prize.