Salil Vadhan

Salil Pravin Vadhan (c. 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 ( Certificate in advanced mathematics after completion of the Tripos, Part 3) and in 1999 at the Massachusetts Institute of Technology (MIT ) at Shafi Goldwasser doctorate ( A study of statistical zero knowledge proofs ). His dissertation received the 2000 ACM Doctoral Dissertation Award. He remained as a post-doctoral researcher at MIT with Madhu Sudan and was 2000/2001 in Avi Wigderson at the Institute for Advanced Study. He was Assistant Professor, in 2004 Associate Professor and in 2007 Gordon McKay Professor of computer science and applied mathematics at Harvard in 2001. 2008 to 2011 he was director of the Harvard Center for Research on Computation and Society ( CRCS ).

2008 he was a Miller Visiting Professor at Berkeley.

It deals with complexity theory in cryptography and data security, zero-knowledge proofs and random 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 ) revealed strong similarities in four previously active as isolated respected fields of research at: pseudo-random generators, random extractors ( randomness extractors ), expander graphs ( sparse graphs that are still well-connected and in many applications in of computer science have ) and error-correcting codes. The combination of expander graphs with Zufallsextraktoren Vadhan discovered with Omer Reingold and Avi Wigderson 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 so that the product graph of the size of the large graph, but the degree of small graphs. The work was influential in theoretical computer science. All three received for the 2009 Gödel Prize.

With Wigderson, Rheingold and Lu succeeded to construct him up to constant factors optimal Zufallsextraktoren.

In 2013 he was Simons Investigator, 2002 to 2004 he was Sloan Fellow and 2007/ 08 he was Guggenheim Fellow.

Writings

• Computational Complexity, in Henk van Tilburg ( eds), Encyclopedia of Cryptography and Security, Springer Verlag 2006
• Rheingold, Wigderson: Entropy Waves, the Zig -Zag Graph Product and New Constant - Degree Expanders, Annals of Mathematics, Volume 155, 2001, pp. 157-187, Arxiv
• Venkatesan Guruswami with, Christopher Umans: Unbalanced Expanders and Randomness Extractors from Parvaresh Vardy codes ", Journal of the ACM, Volume 34, 2009, pp. 1-34
• Shien Jin Ong with: Zero Knowledge and Soundness are Symmetric, Eurocrypt 2007, Lecture Notes in Computer Science, Springer Verlag 2007, 187-209 ( Best Paper Award at Eurocrypt 07)
• 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 Rheingold: Computational Differential Privacy, in: Advances in Cryptology - CRYPTO 2009, Springer Verlag, 2009.