- 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
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!