Salil P. Vadhan
- Vicky Joseph Professor of Computer Science and Applied Mathematics
Salil Vadhan's research centers around the interface between computational complexity theory and cryptography. Complexity theory studies the power and limitations of efficient computation, and cryptography aims to design protocols that withstand adversarial behavior.
Within these general areas, Vadhan has focused on the topics of pseudorandomness, the theory of efficiently generating objects that "look random" despite being constructed with little or no randomness, and zero-knowledge proofs, which are interactive proofs that are convincing yet reveal nothing other than the validity of the assertion being proven.
One of Vadhan's contributions in the area of pseudorandomness was the discovery (with Reingold and Wigderson) of the zig-zag graph product for constructing expander graphs , which has been used in or inspired the solution of several long-standing open questions in theoretical computer science.
In the area of zero-knowledge proofs, Vadhan's work began with his Ph.D. thesis (MIT, 1999), which provided a comprehensive complexity-theoretic understanding of a subclass of zero-knowledge proofs known as statistical zero-knowledge proofs. In the last few years, Vadhan and his students have returned to this topic, and have extended this complexity-theoretic study to include the most general notions of zero knowledge.
As a result, they have managed to reduce or eliminate the complexity assumptions used in many fundamental results about zero-knowledge proofs.
Positions and Employment
Harvard School of Engineering and Applied Sciences
- July 2009-Present: Vicky Joseph Professor of Computer Science and Applied Mathematics (with tenure)
- August 2008-Present: Director, Harvard Center for Research on Computation and Society (CRCS)
- June 2008-July 2008: Consultant
- September 2008-June 2008: Miller Visiting Professor
Harvard School of Engineering and Applied Sciences
- January 2007-June 2009: Gordon McKay Professor of Computer Science and Applied Mathematics (with tenure)
- July 2004-December 2006: Thomas D. Cabot Associate Professor of Computer Science
- June 2001-June 2004: Assistant Professor of Computer Science on the Gordon McKay Endowment
- Fall 2003: Fellow
- 2003-2004: Chair,Radcliffe Cluster on Randomness and Computation
- September 2000-April 2001: Visitor, School of Mathematics
- September 1999-August 2000: NSF Mathematical Sciences Postdoctoral Fellow
- Program Chair, 43rd Annual ACM Symposium on Theory of Computing, San Jose, CA, June 2011
- Member-at-large, ACM Council, July 2010-June 2014
- Local Arrangements Chair, 25th IEEE Conference on Computational Complexity, Cambridge, MA, May 2010
- Organizer, Oberwolfach Meetings on Computational Complexity, November 2009-present
- Co-organizer, DIMACS Workshop on Complexity and Cryptography: Status of Impagliazzo's Worlds, Princeton, NJ, June 2009
- Co-organizer, 60th Birthday Celebration for Leslie Valiant, Bethesda, MD, May 2009
- Organizer, Workshop on Visions for Theoretical Computer Science, Seattle, WA, May 2008.
- Director, Harvard Center for Research on Computation and Society (CRCS), August 2008-present
- SIGACT Committee for the Advancement of Theoretical Computer Science, 2007-present
- Program Chair, 4th Theory of Cryptography Conference (TCC '07)
- Program Chair, 6th International Workshop on Randomization and Approximation Techniques in Computer Science (RANDOM '02).
- Editor, SIAM Journal on Computing, 2005-present
- Editor, Computational Complexity, 2003-present
- Conference Committee, IEEE Conference on Computational Complexity, 2005-2008
- Scientic Board, Electronic Colloquium on Computational Complexity, 2005-present
- Chair, Research Cluster on Randomness & Computation, Radclie Institute for Advanced
- Study, September 2003-August 2004
- Co-organizer, Special Focus on Privacy and Security, Harvard Center for Research on Computation and Society, 2005-present
- Chair, Group on Cryptographic Foundations of Networked Computing, NSF Workshop on the Theory of Networked Computing (ToNC), March 2006
- Program Committees: CRYPTO '00, CCC '01, RANDOM '01, FOCS '01, RANDOM '02, TCC '04, EUROCRYPT '05, CRYPTO '06, STOC '07, CRYPTO '09
- Grant reviewing: NSF Theory of Computing Program (panelist), NSF Cybertrust Program (panelist), Israel Science Foundation, US-Israel Binational Science Foundation
- Extensive journal and conference refereeing
- Godel Prize 2009 for paper, "Entropy Waves, the Zig-Zag Graph Product and New Constant-Degree Expanders" (with Omer Reingold and Avi Wigderson)
- Guggenheim Fellowship, August 2007-July 2008
- Miller Visiting Professorship, UC Berkeley, January 2008-May 2008
- Best Paper Award at CCC 2007 for "Unbalanced Expanders and Randomness Extractors" from Parvaresh-Vardy Codes" (with Venkatesan Guruswami and Christopher Umans)
- Best Paper Award at Eurocrypt 2007 for "Zero Knowledge and Soundness are Symmetric" (with Shien Jin Ong)
- ONR Young Investigator Award, June 2004-May 2007
- Phi Beta Kappa Award for Excellence in Teaching, June 2004
- Radclie Institute Fellowship, September 2003-January 2004
- Alfred P. Sloan Research Fellowship, September 2002-September 2004
- NSF Early Career Development Award, June 2002-May 2007
- Nominated for Everett Mendelsohn Award for Excellence in Mentoring, Spring 2006
- ACM Doctoral Dissertation Award 2000 for the best Ph.D. thesis in computer science
- George M. Sprowls Award (co-winner) for best Ph.D. thesis in Electrical Engineering and Computer Science at MIT
- NSF Mathematical Sciences Postdoctoral Fellowship, September 1999-December 2000
- Charles W. and Jennifer C. Johnson Prize (co-winner) for best paper among MIT Department of Mathematics Graduate Students ("A Complete Promise Problem for Statistical Zero-Knowledge," joint work with A. Sahai, FOCS 1997)
- DOD/NDSEG Graduate Fellowship, 1996-1999
- Churchill Scholarship to study at Churchill College, Cambridge University, 1995-1996. Named sole Loeb Scholar among the ten `95-`96 Churchill Scholars.
- Thomas Temple Hoopes Prize for outstanding undergraduate work at Harvard University, based on undergraduate thesis "The Complexity of Counting."