Salil Vadhan is an American computer scientist. He is Vicky Joseph Professor of Computer Science and Applied Mathematics at
Harvard University
Harvard University is a Private university, private Ivy League research university in Cambridge, Massachusetts, United States. Founded in 1636 and named for its first benefactor, the History of the Puritans in North America, Puritan clergyma ...
. After completing his undergraduate degree in Mathematics and Computer Science at Harvard in 1995, he obtained his PhD in Applied Mathematics from
Massachusetts Institute of Technology
The Massachusetts Institute of Technology (MIT) is a Private university, private research university in Cambridge, Massachusetts, United States. Established in 1861, MIT has played a significant role in the development of many areas of moder ...
in 1999, where his advisor was
Shafi Goldwasser
Shafrira Goldwasser (; born 1959) is an Israeli-American computer scientist. A winner of the Turing Award in 2012, she is the RSA Professor of Electrical Engineering and Computer Science at the Massachusetts Institute of Technology; a professor o ...
. His research centers around the interface between
computational complexity theory
In theoretical computer science and mathematics, computational complexity theory focuses on classifying computational problems according to their resource usage, and explores the relationships between these classifications. A computational problem ...
and
cryptography
Cryptography, or cryptology (from "hidden, secret"; and ''graphein'', "to write", or ''-logy, -logia'', "study", respectively), is the practice and study of techniques for secure communication in the presence of Adversary (cryptography), ...
. He focuses on the topics of
pseudorandomness
A pseudorandom sequence of numbers is one that appears to be statistically random, despite having been produced by a completely deterministic and repeatable process. Pseudorandom number generators are often used in computer programming, as tradi ...
and
zero-knowledge proof
In cryptography, a zero-knowledge proof (also known as a ZK proof or ZKP) is a protocol in which one party (the prover) can convince another party (the verifier) that some given statement is true, without conveying to the verifier any information ...
s. His work on the
zig-zag product
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, is a Graph operations, binary operation which takes a large graph (G) and a small graph (H) and produces a graph that approximately inherits the size of the large ...
, with
Omer Reingold
Omer Reingold () is an Israeli computer scientist. He is the Rajeev Motwani professor of computer science in the Computer Science Department at Stanford University and the director of thSimons Collaboration on the Theory of Algorithmic Fairness ...
and
Avi Wigderson
Avi Wigderson (; born 9 September 1956) is an Israeli computer scientist and mathematician. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America ...
, was
awarded the 2009
Gödel Prize
The Gödel Prize is an annual prize for outstanding papers in the area of theoretical computer science, given jointly by the European Association for Theoretical Computer Science (EATCS) and the Association for Computing Machinery Special Inter ...
.
Contributions
Zig-zag graph product for constructing expander graphs
One of the main contributions of his work is a new type of graph product, called the
zig-zag product
In graph theory, the zig-zag product of regular graphs G,H, denoted by G \circ H, is a Graph operations, binary operation which takes a large graph (G) and a small graph (H) and produces a graph that approximately inherits the size of the large ...
.
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 that 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
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 that beat the "eigenvalue bound."
Vadhan also came up with another simplified approach to the undirected
ST-connectivity
In computer science, st-connectivity or STCON is a decision problem asking, for vertices ''s'' and ''t'' in a directed graph, if ''t'' is reachability, reachable from ''s''.
Formally, the decision problem is given by
:.
Complexity
On a seque ...
problem following Reingold's breakthrough result.
Also the zig-zag product was useful in
Omer Reingold
Omer Reingold () is an Israeli computer scientist. He is the Rajeev Motwani professor of computer science in the Computer Science Department at Stanford University and the director of thSimons Collaboration on the Theory of Algorithmic Fairness ...
's proof that
SL=
L.
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 Goldreich
Oded Goldreich (; born 1957) is a professor of computer science at the faculty of mathematics and computer science of the Weizmann Institute of Science, Israel. His research interests lie within the theory of computation and are, specifically, ...
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 Reingold
Omer Reingold () is an Israeli computer scientist. He is the Rajeev Motwani professor of computer science in the Computer Science Department at Stanford University and the director of thSimons Collaboration on the Theory of Algorithmic Fairness ...
, and
Avi Wigderson
Avi Wigderson (; born 9 September 1956) is an Israeli computer scientist and mathematician. He is the Herbert H. Maass Professor in the school of mathematics at the Institute for Advanced Study in Princeton, New Jersey, United States of America ...
, he gave the first construction of
randomness extractor
A randomness extractor, often simply called an "extractor", is a function, which being applied to output from a weak entropy source, together with a short, uniformly random seed, generates a highly random output that appears Independent and identic ...
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.
Recognition
Vadhan was elected as an
ACM Fellow
ACM Fellowship is an award and fellowship that recognises outstanding members of the Association for Computing Machinery (ACM). The title of ACM Fellow
A fellow is a title and form of address for distinguished, learned, or skilled individuals ...
in 2018 for "advancing computational complexity and cryptography, and for promoting public support for theoretical computer science."
References
External links
Salil Vadhan's home page at Harvard
{{DEFAULTSORT:Vadhan, Salil
Harvard John A. Paulson School of Engineering and Applied Sciences faculty
American theoretical computer scientists
Harvard College alumni
Massachusetts Institute of Technology School of Science alumni
Gödel Prize laureates
Living people
Simons Investigator
2018 fellows of the Association for Computing Machinery
Year of birth missing (living people)