HOME

TheInfoList



OR:

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)