Tuesday, May 08, 2007
Gödel Prize 2007
The Gödel prize 2007, co-sponsored by EATCS and ACM SIGACT, is awarded to Alexander A. Razborov and Steven Rudich for their paper "Natural Proofs", Journal of Computer and System Sciences, Vol. 55, No. 1, 1997, pp. 24-35. (The conference version of the paper was first presented at the Twenty-sixth Annual ACM Symposium on Theory of computing, Montreal, Quebec, Canada. 1994, pp. 204 - 213.)
For discussions of the importance of this result in computational complexity, see here, and here. (Two posts from two of my favourite blogs.) Wikipedia has an entry on natural proofs.
Congratulations to Alexander A. Razborov and Steven Rudich, two outstanding members of the TCS community, for the award.
Addendum: The citation for the award is available here.
Posted by Luca Aceto at 11:21 a.m.