Salil Vadhan is an American computer scientist. He holds the position of Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University. He earned his undergraduate degree in Mathematics and Computer Science from Harvard in 1995. In 1999, he completed his PhD in Applied Mathematics at the Massachusetts Institute of Technology, with Shafi Goldwasser as his advisor. His research focuses on the connection between computational complexity theory and cryptography. He studies topics such as pseudorandomness and zero-knowledge proofs. His work on the zig-zag product, conducted with Omer Reingold and Avi Wigderson, was honored with the 2009 Gödel Prize.
Contributions
One of the main contributions of his work is a new type of graph product, called the zig-zag product.
When combining a large graph with a small graph using the zig-zag product, the resulting graph has a size similar to the large graph, a degree similar to the small graph, and expansion properties influenced by both. Repeating this process allows for the creation of simple, explicit examples of expanders with a constant degree, of any size, starting from one small expander.
Understanding and analyzing the zig-zag product is easier when thinking of expanders as tools that spread out information, like waves moving entropy from one place to another. In this way, combining two expanders through the zig-zag product helps combine their spreading effects.
A version of this product can be used to improve extractors, which are tools for removing randomness from data. This method creates the first explicit extractors that require a seed length depending only on how much entropy is missing from the source, rather than the source's total length. These extractors are highly effective at recovering most of the entropy from sources with very high minimum entropy. These improvements have led to new types of expanders with constant degree that perform better than previous limits based on eigenvalues.
Vadhan also developed a simpler method for solving the undirected ST-connectivity problem, inspired by Reingold's major discovery. Additionally, the zig-zag product played a key role in Reingold's proof that the class SL equals the class L.
His research focuses on using complexity-theoretic methods to study the strengths and limits of zero-knowledge proofs. In a series of papers with Oded Goldreich and Amit Sahai, he explored the class SZK, which includes problems that can be solved with statistical zero-knowledge proofs. He identified the properties of SZK and showed that this class remains unchanged under certain operations. Recently, his work has aimed to extend these ideas beyond the SZK class.
With Lu, Reingold, and Wigderson, he created the first randomness extractors that are nearly optimal, achieving a major breakthrough in a long line of research on this topic.
With Trevisan, Zuckerman, Kamp, and Rao, he developed a theory for extracting randomness (and compressing data) from samplable sources, which are random sources generated by an unknown efficient algorithm.
Recognition
In 2018, Vadhan was chosen as an ACM Fellow for helping to develop computational complexity and cryptography, and for encouraging more people to support theoretical computer science.