The 2009 Gödel Prize for outstanding papers in the area of theoretical computer science is awarded to
(1) Entropy waves, the zig-zag graph product and new constant degree expanders. Omer Reingold, Salil Vadhan and Avi Wigderson, Annals of Mathematics, Vol 155, (2002), 157-187and
(2) Undirected connectivity in Log-Space. Omer Reingold, Journal of ACM, Vol 55 (4) (2007).
Expander graphs, which were introduced by Pinsker in 1973, are constant degree graphs in which each small set of vertices has a large number of outside neighbors. Due to the combination of high connectivity and sparsity (lowdegree), these graphs have proved to be of enormous importance to the theory of computation. It is not difficult to see that a random graph is a good expander but as one of the main applications of expanders is to replace randomness by deterministic choices it is crucial to have efficient and deterministic constructions of expanders. Early deterministic explicit constructions of expanders were algebraic in nature, often yielding graphs only of certain sizes with certain degrees.
The first of the two awarded papers gives a completely combinatorial explicit construction of a rich family of expander graphs. The key to the construction is the introduction of the Zig-Zag graph product that makes it possible to iteratively construct large expanders from smaller expanders preserving degree and connectivity. In addition to enabling the construction of expanders, this tool has proved remarkably useful in other contexts as well.
The second awarded paper uses the Zig-Zag graph product to solve one of the most famous and fundamental de-randomization problems in computational complexity theory: to deterministically and efficiently determine connectivity, find whether there is a path between two nodes, in undirected graphs. This problem is easy to solve deterministically for expander graphs. The idea for solving it for general undirected graphs is to reduce the connectivity of a general graph to that of an expander graph. The key observation is that any connected graph is a (very) weak expander and iterating an operation like the Zig-Zag product makes it possible to turn the graph into an expander of only moderately larger size. The new algorithm for undirected connectivity is oflogarithmic space complexity, proving that L = SL, resolving a 25-year-old open problem.
Finally, the set of ideas used in these two papers have already been used to obtain other spectacular results, the most prominent being a new combinatorial proof of the PCP-theorem by Dinur. Other advances are sure to come.