Salil Vadhan

Salil Vadhan
Salil Vadhan.jpg
Salil Vadhan
Staatsbürgerschaft Vereinigte Staaten
Ausbildung Harvard Universität (Ba)
Massachusetts Institute of Technology (PhD)
Bekannt für Zick-Zack-Produkt
Auszeichnungen
Wissenschaftliche Karriere
Felder Computerkomplexitätstheorie, Kryptographie
Institutionen Harvard Universität
Doktorand SHAFI GOLDSER

Salil Vadhan ist ein amerikanischer Informatiker. Er ist Vicky Joseph Professor für Informatik und hat Mathematik angewendet Harvard Universität.[1] Nach Abschluss seines Bachelor -Abschlusses in Mathematik und Informatik in Harvard im Jahr 1995 promovierte er in angewandter Mathematik von angewandter Mathematik aus Massachusetts Institute of Technology 1999, wo sein Berater war SHAFI GOLDSER.[2] Seine Forschungszentren um die Schnittstelle zwischen Computerkomplexitätstheorie und Kryptographie. Er konzentriert sich auf die Themen von Pseudorandomness und Null-Wissen-Beweise. Seine Arbeit an der Zick-Zack-Produkt, mit Omer Reingold und Avi Wigderson, wurde mit dem 2009 ausgezeichnet Gödel -Preis.[3]

Contributions

Zick-Zack-Diagrammprodukt zum Erstellen von Expandergraphen

Einer der Hauptbeiträge seiner Arbeit ist eine neue Art von Graph -Produkt, genannt die Zick-Zack-Produkt.

Ein Produkt eines großen Diagramms mit einem kleinen Diagramm, das resultierende Diagramm erbringt (ungefähr) seine Größe von der großen, ITS, ITS Grad von der kleinen und seine Expansionseigenschaften von beiden. Die Iteration liefert einfache explizite Konstruktionen von Expositionen mit konstantem Grad jeder Größe, beginnend mit einem Expander konstanter Größe.

Entscheid für die Intuition und einfache Analyse der Eigenschaften des Zick-Zack aufgelöst. In diesen Begriffen bietet das Graph -Produkt die konstruktive Einmischung von zwei solcher Wellen.

Eine Variante dieses Produkts kann auf Extraktoren angewendet werden, was den ersten expliziten Extraktoren verleiht, deren Samenlänge abhängt(poly) logarithmisch Nur auf dem Entropiemangel der Quelle (und nicht ihrer Länge) und fast die gesamte Entropie von hohen Min-Entropie-Quellen. Diese hohen Min-Entropie-Extraktoren haben mehrere interessante Anwendungen, darunter die ersten expliziten Expositionen mit konstantem Grad, die die "Eigenwerte gebunden" übertreffen.

Vadhan entwickelte auch einen weiteren vereinfachten Ansatz[4] zu den Ungerichteten ST-Verbindlichkeit Problem nach dem Durchbruch von Reingold. Auch das Zick-Zack-Produkt war nützlich in Omer ReingoldBeweis das Sl=L.

Null-Wissen-Beweise

Seine Arbeit in diesem Bereich ist es, komplexitätstheoretische Methoden anzuwenden, um die Kraft und Einschränkungen von Null-Wissen-Beweisen zu verstehen. In einer Reihe von Papieren mit Od Goldreich und Amit SahaiSie erlangten ein gründliches Verständnis der Klasse SZK mit Problemen mit statistischen Null-Wissen-Beweisen, charakterisierten die Klasse SZK und bewiesen, dass SZK unter verschiedenen Operationen geschlossen ist. Kürzlich war seine Arbeit, an dem Null-Wissen-Beweis hinaus zu arbeiten, das über die Grenzen der SZK-Klasse hinausgeht.

Zufälligkeit Extraktoren

Mit lu, Omer Reingold, und Avi WigdersonEr gab den ersten Bau von Zufälligkeit Extraktoren Das sind "optimal bis zu konstanten Faktoren" und erreichen in einem Jahrzehnt der Arbeit zu diesem Thema einen Meilenstein.

Mit Trevisan, Zuckerman, Kamp und Rao entwickelte er eine Theorie der Zufälligkeitsextraktion (und Datenkomprimierung) aus Stichprobenquellen, die zufällige Quellen sind, die durch einen (unbekannten) effizienten Algorithmus erzeugt werden.

Erkennung

Vadhan wurde als als gewählt ACM Fellow Im Jahr 2018 für "Fortschritt der Computerkomplexität und Kryptographie und zur Förderung der öffentlichen Unterstützung für theoretische Informatik".[5]

Verweise

  1. ^ Harvard -Fakultätsverzeichnis.
  2. ^ Salil Vadhan Bei der Mathematik Genealogie -Projekt.
  3. ^ 2009 Gödel Prize, Europäische Vereinigung für theoretische Informatik.
  4. ^ Rozenman-Vadhan.
  5. ^ 2018 ACM -Stipendiaten, die für entscheidende Erfolge geehrt wurden, die das digitale Zeitalter stützen, Verband für Rechenmaschinen, 5. Dezember 2018

Externe Links