Loading ...
Sorry, an error occurred while loading the content.

[Computational Complexity] Gödel Prize

Expand Messages
  • Lance
    This year s Gödel Prize has been awarded to two papers. - Undirected Connectivity in Log-Space by Omer Reingold - Entropy Waves, the Zig-Zag Graph Product and
    Message 1 of 1 , May 21, 2009
      This year's Gödel Prize has been awarded to two papers.
      I consider Reingold's paper the second best result of the decade after "Primes in P" which won the prize in 2006. Reingold settled a long-standing open question deterministically showing how to get from point A to point B in an undirected graph using memory equivalent to remembering a constant number of vertices.

      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!

      Posted By Lance to Computational Complexity at 5/21/2009 06:24:00 AM
    Your message has been successfully submitted and would be delivered to recipients shortly.