Salil Vadhan
Encyclopedia
Salil Vadhan is Vicky Joseph Professor of Computer Science and Applied Mathematics at Harvard University
. He obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology
in 1999, where his advisor was Shafi Goldwasser
. His research centers around the interface between computational complexity theory
and cryptography
. He focuses on the topics of pseudorandomness and zero-knowledge proofs. His work on zig-zag product
, with Omer Reingold
and Avi Wigderson
, was
awarded the 2009 Godel Prize
.
called the zig-zag product
.
Taking a product of a large graph with a small graph, the resulting
graph inherits (roughly) its size from the large one, its degree from
the small one, and its expansion properties from both! Iteration
yields simple explicit constructions of constant-degree expanders of
every size, starting from one constant-size expander.
Crucial to the intuition and simple analysis of the properties of the zig-zag product is the view of expanders as functions which act as “entropy wave” propagators — they transform probability distributions in which entropy is concentrated in one area to distributions where that concentration is dissipated. In these terms, the graph product affords the constructive interference of two such waves.
A variant of this product can be applied to extractors, giving the
first explicit extractors whose seed length depends
(poly)logarithmically on only the entropy deficiency of the source
(rather than its length) and that extract almost all the entropy of
high min-entropy sources. These high min-entropy extractors have
several interesting applications, including the first constant-degree
explicit expanders which beat the “eigenvalue bound.”
Vadhan also came up with another simplified approach to the undirected ST-connectivity
problem following Reingold's breakthrough result.
Also the zig-zag product was useful in Omer Reingold
's proof that SL
=L
.
and Amit Sahai, they gained thorough understanding of the class SZK of problems possessing statistical zero-knowledge proofs, characterized the class SZK and proved that SZK is closed under various operations. Recently his work was trying to work on the zero-knowledge proof beyond the confines of SZK class.
, and Avi Wigderson
, he gave the first construction of randomness extractor
s that are “optimal up to constant factors,” reaching a milestone in a decade of work on the subject.
With Trevisan, Zuckerman, Kamp, and Rao, he developed a theory of randomness extraction (and data compression) from samplable sources, which are random sources generated by an (unknown) efficient algorithm.
Harvard University
Harvard University is a private Ivy League university located in Cambridge, Massachusetts, United States, established in 1636 by the Massachusetts legislature. Harvard is the oldest institution of higher learning in the United States and the first corporation chartered in the country...
. He obtained his PhD in Applied Mathematics from Massachusetts Institute of Technology
Massachusetts Institute of Technology
The Massachusetts Institute of Technology is a private research university located in Cambridge, Massachusetts. MIT has five schools and one college, containing a total of 32 academic departments, with a strong emphasis on scientific and technological education and research.Founded in 1861 in...
in 1999, where his advisor was Shafi Goldwasser
Shafi Goldwasser
Shafrira Goldwasser is the RSA Professor of electrical engineering and computer science at MIT, and a professor of mathematical sciences at the Weizmann Institute of Science, Israel.-Biography:...
. His research centers around the interface between computational complexity theory
Computational complexity theory
Computational complexity theory is a branch of the theory of computation in theoretical computer science and mathematics that focuses on classifying computational problems according to their inherent difficulty, and relating those classes to each other...
and cryptography
Cryptography
Cryptography is the practice and study of techniques for secure communication in the presence of third parties...
. He focuses on the topics of pseudorandomness and zero-knowledge proofs. His work on zig-zag product
Zig-zag product
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, takes a large graph and a small graph , and produces a graph that approximately inherits the size of the large one but the degree of the small one...
, with Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
and Avi Wigderson
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
, was
awarded the 2009 Godel Prize
Gödel Prize
The Gödel Prize is a prize for outstanding papers in theoretical computer science, named after Kurt Gödel and awarded jointly by the European Association for Theoretical Computer Science and the Association for Computing Machinery Special Interest Group on Algorithms and Computation Theory .The...
.
Zig-zag Graph Product for Constructing Expander Graphs
One of the main contribution of his work is a new type of graph product,called the zig-zag product
Zig-zag product
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, takes a large graph and a small graph , and produces a graph that approximately inherits the size of the large one but the degree of the small one...
.
Taking a product of a large graph with a small graph, the resulting
graph inherits (roughly) its size from the large one, its degree from
the small one, and its expansion properties from both! Iteration
yields simple explicit constructions of constant-degree expanders of
every size, starting from one constant-size expander.
Crucial to the intuition and simple analysis of the properties of the zig-zag product is the view of expanders as functions which act as “entropy wave” propagators — they transform probability distributions in which entropy is concentrated in one area to distributions where that concentration is dissipated. In these terms, the graph product affords the constructive interference of two such waves.
A variant of this product can be applied to extractors, giving the
first explicit extractors whose seed length depends
(poly)logarithmically on only the entropy deficiency of the source
(rather than its length) and that extract almost all the entropy of
high min-entropy sources. These high min-entropy extractors have
several interesting applications, including the first constant-degree
explicit expanders which beat the “eigenvalue bound.”
Vadhan also came up with another simplified approach to the undirected ST-connectivity
ST-connectivity
In computer science and computational complexity theory, st-connectivity or STCON is a decision problem asking, for vertices s and t in a directed graph, if t is reachable from s.Formally, the decision problem is given by- Complexity :...
problem following Reingold's breakthrough result.
Also the zig-zag product was useful in Omer Reingold
Omer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
's proof that SL
SL (complexity)
In computational complexity theory, SL is the complexity class of problems log-space reducible to USTCON , which is the problem of determining whether there exists a path between two vertices in an undirected graph, otherwise described as the problem of determining whether two vertices are in the...
=L
L (complexity)
In computational complexity theory, L is the complexity class containing decision problems which can be solved by a deterministic Turing machine using a logarithmic amount of memory space...
.
Zero-Knowledge Proofs
His work in this area is to use complexity-theoretic methods to understand the power and limitations of zero-knowledge proofs. In a series of papers with Oded GoldreichOded Goldreich
Oded Goldreich is a professor of Computer Science at the Faculty of Mathematics and Computer Science of Weizmann Institute of Science, Israel. His research interests lie within the theory of computation...
and Amit Sahai, they gained thorough understanding of the class SZK of problems possessing statistical zero-knowledge proofs, characterized the class SZK and proved that SZK is closed under various operations. Recently his work was trying to work on the zero-knowledge proof beyond the confines of SZK class.
Randomness Extractors
With Lu, Omer ReingoldOmer Reingold
Omer Reingold is a faculty member of the Foundations of Computer Science Group at the Weizmann Institute of Science, Israel. He received the 2005 Grace Murray Hopper Award for his work in finding a deterministic logarithmic-space algorithm for ST-connectivity in undirected graphs...
, and Avi Wigderson
Avi Wigderson
Avi Wigderson is an Israeli mathematician and computer scientist, a professor of mathematics at the Institute for Advanced Study in Princeton. His research interests include complexity theory, parallel algorithms, graph theory, cryptography, distributed computing, and neural...
, he gave the first construction of randomness extractor
Randomness extractor
A randomness extractor, often simply called "an extractor," is a function which, when applied to a high-entropy source , generates a random output that is shorter, but uniformly distributed...
s that are “optimal up to constant factors,” reaching a milestone in a decade of work on the subject.
With Trevisan, Zuckerman, Kamp, and Rao, he developed a theory of randomness extraction (and data compression) from samplable sources, which are random sources generated by an (unknown) efficient algorithm.