Salil Vadhan
SalilVadhan
2003–2004
Harvard University
Computer Science
Randomness and Computation

Salil Vadhan, an assistant professor of computer science at Harvard University, conducts research in the theory of computation, the field that studies the mathematical laws governing efficient computation. The general goals of this area are to understand which computational problems can be solved in principle, to determine the resources (such as time and memory) needed to solve such problems, and to find applications of this understanding in computer science, mathematics, and other fields.

As a member of the Radcliffe cluster on randomness and computation, Vadhan will focus on pseudorandomness, the theory of efficiently generating objects that “look random” despite being constructed with little or no randomness. One motivation for this study is to understand whether randomized computations, ones that “toss coins,” can be substantially more efficient than deterministic ones. In addition, the theory of pseudo-randomness has application to and unifies a wide variety of other seemingly unrelated topics in cryptography, information theory, graph theory, and computational complexity.

Vadhan holds an AB in mathematics and computer science from Harvard and a PhD in applied mathematics from MIT. His thesis was awarded the ACM/Doctoral Dissertation Award in 2000. He is a recipient of a Sloan Research Fellowship and a National Science Foundation Career Award.

This information is accurate as of the fellowship year indicated for each fellow.