Vadhan shares ACM's 2009 Godel Prize for zig-zag graph

NEW YORK, NY - May 19, 2009 - ACM's Special Interest Group on Algorithms and Computing Theory (SIGACT) has recognized the contributions of three computer scientists, including Salil Vadhan, Gordon McKay Professor of Computer Science and Applied Mathematics at the Harvard School of Engineering and Applied Sciences (SEAS), who developed a new type of graph that enables the construction of large expander graphs, which play an important role in designing robust computer networks and constructing theories of error-correcting computer codes.

Using the new zig-zag graph, this technique was able to solve one of the most intriguing open problems in computational complexity theory, that of detecting a path from one node to another in very small storage for undirected graphs (in which the nodes are connected by lines with no direction).

Vadhan and his co-authors Omer Reingold and Avi Wigderson will receive the 2009 Godel Prize, presented by SIGACT and the European Association for Theoretical Computer Science (EATCS), for outstanding papers in theoretical computer science at the ACM Symposium on the Theory of Computing (STOC) May 31 - June 2, in Bethesda, MD.

Salil Vadhan is Gordon McKay Professor of Computer Science and Applied Mathematics, and Director of the Center for Research on Computation and Society at SEAS.

He was a visiting professor at the University of California Berkeley and a visiting member of the School of Mathematics, Institute for Advanced Study. He received a Ph.D. in applied mathematics from the Massachusetts Institute of Technology (MIT) and won the 2000 ACM Doctoral Dissertation award for his Ph.D. thesis.

The recipient of a Certificate of Advanced Study in Mathematics from Churchill College, Cambridge University, he earned an A.B. in mathematics and computer science from Harvard University.

The Godel Prize, which includes an award of $5,000, is named in honor of Kurt Godel, who was born in Austria-Hungary (now the Czech Republic) in 1906. Godel's work has had immense impact upon scientific and philosophical thinking in the 20th century. The award recognizes his major contributions to mathematical logic and the foundations of computer science.

Adapted from the ACM Press Release.