Avi Wigderson and Colleagues Honored with 2009 Gödel Prize

The 2009 Gödel Prize for outstanding papers in theoretical computer science will be awarded to Avi Wigderson, Herbert A. Maass Professor in the School of Mathematics, and former Visitors Omer Reingold (1999-2003) and Salil Vadhan (2000-01). The recipients were selected for their development of a new type of graph product that improves the design of robust computer networks and resolved open questions on error correction and derandomization. The papers cited are "Entropy Waves, the Zig-Zag Graph Product, and New Constant Degree Expanders" by all three (conceived and written at IAS) and a subsequent paper, "Undirected Connectivity in Log-Space," by Reingold. The prize is named for Kurt Gödel, who was a Member (1933-34, 1935, 1938, 1940-53) of the Institute and subsequently served on the Faculty (1953-78). The Gödel Prize is awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory and will be presented at the ACM Symposium on the Theory of Computing, held from May 31 to June 2, in Bethesda, Maryland.