[Computational Complexity] Gödel Prize
- This year's Gödel Prize has been awarded to two papers.
The zig-zag paper developed a new construction of constant-degree expanders. We already had simpler expander constructions but the zig-zag technique gave us a recursive way to think about expanders that Reingold drew on for his paper.This is the first Gödel prize for each of these authors and I'm especially happy to see Wigderson, perhaps the best complexity theorist of our generation, take the prize. Avi could have easily won it earlier for his work on zero-knowledge, derandomization, circuit complexity or many other topics.Congrats to All!
- Undirected Connectivity in Log-Space by Omer Reingold
- Entropy Waves, the Zig-Zag Graph Product and New Constant Degree Expanders by Reingold, Salil Vadhan and Avi Wigderson
Posted By Lance to Computational Complexity at 5/21/2009 06:24:00 AM