Salil Vadhan

rdf:langString Salil Vadhan

rdf:langString 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). 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.