Salil Vadhan

Vadhan, Oberwolfach 2012

Salil Pravin Vadhan (* around 1965) is an American computer scientist.

Vadhan studied at Harvard University with a bachelor's degree summa cum laude in 1995 with Leslie Valiant (The complexity of counting), at Churchill College, Cambridge University (certificate in higher mathematics after completing the Tripos, Part 3) and was at the Massachusetts Institute in 1999 of Technology (MIT) at Shafi Goldwasser (A study of statistical zero knowledge proofs). His dissertation received the ACM Doctoral Dissertation Award in 2000. He stayed as a post-doctoral student at MIT with Madhu Sudan and was with Avi Wigderson at the Institute for Advanced Study in 2000/2001 . He became Assistant Professor in 2001, Associate Professor in 2004 and Gordon McKay Professor of Computer Science and Applied Mathematics at Harvard in 2007 . From 2008 to 2011 he was director of the Harvard Center for Research on Computation and Society (CRCS).

In 2008 he was Miller Visiting Professor at Berkeley.

He deals with complexity theory in cryptography and data security, zero-knowledge proofs, and chance in calculations (such as pseudo-random numbers ). In his dissertation he examined the complexity of a large class of zero-knowledge proofs, statistical zero-knowledge proofs. He also worked with Oded Goldreich .

The research of Vadhan and others (such as Luca Trevisan ) uncovered strong similarities in four previously viewed as separate active research fields: pseudo-random generators, randomness extractors, expander graphs (light graphs that are nevertheless well networked and many applications in computer science) and error-correcting codes . From the connection of expander graphs with random extractors, Vadhan and Omer Reingold and Avi Wigderson discovered the zig-zag product of graphs for the construction of expander graphs. The zig-zag product is a new type of graph product in which a product of a large and a small graph is formed in such a way that the product graph is the size of the large graph but the degree of the small graph. The work was influential in theoretical computer science. All three received the Gödel Prize for this in 2009 .

With Wigderson, Rheingold and Lu he succeeded in constructing optimal random extractors apart from constant factors.

In 2013 he became Simons Investigator, from 2002 to 2004 he was a Sloan Fellow and in 2007/08 he was a Guggenheim Fellow . He has been a Fellow of the Association for Computing Machinery since 2018 .

Fonts

• Computational Complexity , in Henk van Tilburg (Ed.), Encyclopedia of Cryptography and Security, Springer Verlag 2006
• The complexity of counting in sparse, regular, and planar graphs , SIAM Journal on Computing, Volume 31, 2001, pp. 398-427
• with Rheingold, Wigderson: Entropy Waves, the Zig-Zag Graph Product and New Constant-Degree Expander , Annals of Mathematics, Volume 155, 2001, pp. 157-187, Arxiv
• with Venkatesan Guruswami, Christopher Umans: Unbalanced Expanders and Randomness Extractors from Parvaresh Vardy Codes , Journal of the ACM, Volume 34, 2009, pp. 1-34
• with Shien Jin Ong: Zero Knowledge and Soundness are Symmetric , Eurocrypt 2007, Lecture Notes in Computer Science, Springer Verlag 2007, 187–209 (Best Paper Award at Eurocrypt 07)
• with Jonathan Ullman: PCPs and the hardness of generating private synthetic data , in Yuval Ishai (editor), Proceedings of the 8th IACR Theory of Cryptography Conference (TCC `11), Lecture Notes on Computer Science 5978, Springer Verlag 2011, p. 572 -587.
• with Ilya Mironov, Omkant Pandey, Omer Reingold: Computational Differential Privacy , In: Advances in Cryptology - CRYPTO 2009. Springer Verlag 2009

Web links

• Homepage

Individual evidence

1. ↑ Salil Vadhan in the Mathematics Genealogy Project (English)