Salil Vadhan

Salil Pravin Vadhan (* um 1965) ist ein US-amerikanischer Informatiker.

Vadhan studierte an der Harvard University mit dem Bachelor-Abschluss summa cum laude 1995 bei Leslie Valiant (The complexity of counting), am Churchill College der Universität Cambridge (Zertifikat in höherer Mathematik nach Absolvierung der Tripos, Teil 3) und wurde 1999 am Massachusetts Institute of Technology (MIT) bei Shafi Goldwasser promoviert (A study of statistical zero knowledge proofs)^[1]. Seine Dissertation erhielt 2000 den ACM Doctoral Dissertation Award. Er blieb als Post-Doktorand am MIT bei Madhu Sudan und war 2000/2001 bei Avi Wigderson am Institute for Advanced Study. 2001 wurde er Assistant Professor, 2004 Associate Professor und 2007 Gordon McKay Professor für Informatik und Angewandte Mathematik in Harvard. 2008 bis 2011 war er Direktor des Harvard Center for Research on Computation and Society (CRCS).

2008 war er Miller-Gastprofessor in Berkeley.

Er befasst sich mit Komplexitätstheorie in der Kryptographie und Datensicherheit, Zero-Knowledge-Beweisen und mit Zufall in Berechnungen (wie Pseudozufallszahlen). In seiner Dissertation untersuchte er die Komplexität einer großen Klasse von Zero-Knowledge-Beweisen, statistischen Zero-Knowledge-Beweisen. Dabei arbeitete er auch mit Oded Goldreich zusammen.

Die Forschungen von Vadhan und anderen (wie Luca Trevisan) deckten starke Gemeinsamkeiten in vier zuvor als getrennt angesehene aktive Forschungsfeldern auf: Pseudozufallsgeneratoren, Zufalls-Extraktoren (randomness extractors), Expander-Graphen (lichte Graphen, die trotzdem gut vernetzt sind und viele Anwendungen in der Informatik besitzen) und fehlerkorrigierenden Codes. Aus der Verbindung von Expander-Graphen mit Zufallsextraktoren entdeckte Vadhan mit Omer Reingold und Avi Wigderson das zig-zag-Produkt von Graphen zur Konstruktion von Expandergraphen. Das Zig-zag-Produkt ist eine neue Art von Graphenprodukt, bei dem ein Produkt aus einem großen und einem kleinen Graphen so gebildet wird, dass der Produktgraph von der Größe des großen Graphen ist, aber vom Grad des kleinen Graphen. Die Arbeit war einflussreich in der theoretischen Informatik. Alle drei erhielten dafür 2009 den Gödel-Preis.

Mit Wigderson, Rheingold und Lu gelang es ihm bis auf konstante Faktoren optimale Zufallsextraktoren zu konstruieren.

2013 wurde er Simons Investigator, 2002 bis 2004 war er Sloan Fellow und 2007/08 war er Guggenheim Fellow. Seit 2018 ist er Fellow der Association for Computing Machinery.

Schriften[Bearbeiten | Quelltext bearbeiten]

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