Avi Wigderson (hebräisch: אבי ויגדרזון; geboren am 9. September 1956) ist ein israelischer Informatiker und Mathematiker. Er ist der Herbert-H.-Maass-Professor an der Schule für Mathematik am Institute for Advanced Study in Princeton, New Jersey, Vereinigte Staaten. Seine Forschungsinteressen umfassen die Komplexitätstheorie, parallele Algorithmen, Graphentheorie, Kryptographieund verteiltes Rechnen. Wigderson erhielt den Abel-Preis im Jahr 2021 und den Turing-Award im Jahr 2023 für seine transformative Arbeit in der theoretischen Informatik.
Wigdersons Arbeit konzentriert sich auf die Rolle des Zufalls in der Berechnungund die Struktur effizienter Algorithmen. Er ist eine führende Figur in der Komplexitätstheorie, mit entscheidenden Beiträgen zum Verständnis der Macht randomisierter Algorithmen, zur Konstruktion von Expander-Graphen über das Zickzack-Produktund zu den Grundlagen von Zero-Knowledge-Beweisen.
Frühes Leben und Ausbildung
Wigderson wurde in Haifa, Israel, am 9. September 1956 als Kind von Holocaust-Überlebenden geboren. Er besuchte die Hebräische Reali-Schule in Haifa. Im Jahr 1977 begann er sein Grundstudium am Technion Israel Institute of Technology, wo er 1980 abschloss. Am Technion lernte er seine Frau, Edna, kennen. Anschließend absolvierte er ein Graduiertenstudium an der Princeton University und erwarb 1983 einen Ph.D. in Informatik. Seine Doktorarbeit, betitelt„Studies in Computational Complexity,“ wurde von Richard Lipton betreut. Wigderson wird zugeschrieben, das Feld der computationalen Komplexität erheblich bereichert zu haben.
Akademische Karriere
Nach kurzen Positionen an der University of California, Berkeley, am IBM-Almaden-Forschungszentrum in San Jose, Kalifornien, und am Mathematical Sciences Research Institutein Berkeley kehrte Wigderson 1986 nach Israel zurück, um der Fakultät der Hebräischen Universität von Jerusalem beizutreten. Er erhielt 1987 eine Festanstellungund wurde 1991 ordentlicher Professor. Im Jahr 1999 übernahm er außerdem eine Position am Institute for Advanced Study, und 2003 gab er seine Position an der Hebräischen Universität auf, um die Rolle des Herbert-H.-Maass-Professors am Institute in Princeton zu übernehmen..
Am Institute for Advanced Study hat sich Wigderson auf das Zusammenspiel zwischen computationaler Komplexität, Mathematikund Kryptographie konzentriert. Er hat dazu beigetragen, eine Generation von Forschern in diesen Bereichen anzuführen.
Wichtigste Beiträge
Wigderson untersuchte die grundlegende Frage, ob Zufall für effiziente Berechnung notwendig ist. Mit Noam Nisanund Russell Impagliazzo zeigte Wigderson, dass für bestimmte Algorithmen, die auf zufälligen Münzwürfen basieren, ein fast ebenso schneller deterministischer Algorithmus existiert, der keinen Zufall verwendet, sofern bestimmte Bedingungen erfüllt sind. Diese Forschungslinie, die auf dem Konzept der Pseudozufälligkeit aufbaut, ist ein Eckpfeiler der theoretischen Informatik..
In Zusammenarbeit mit Omer Reingoldund Salil Vadhan entwickelte Wigderson das Zickzack-Produkt, eine kombinatorische Operation auf Graphen, die kleinere Graphen kombiniert, um größere, gut verbundene zu erzeugen. Dieses Konzept verbindet Komplexitätstheorie, Graphentheorieund Gruppentheorie, mit Anwendungen, die vom Verständnis, wie man ein Labyrinth navigiert, bis zur Konstruktion effizienter Expander-Graphen reichen. Das Zickzack-Produkt wurde zu einem wichtigen Werkzeug in der theoretischen Informatik..
Wigderson hat zusammen mit Silvio Micaliund Oded Goldreich gezeigt, dass Zero-Knowledge-Beweise verwendet werden können, um öffentliche Ergebnisse über geheime Daten zu verifizieren, ohne die zugrunde liegenden Geheimnisse preiszugeben. Diese Arbeit ist eine grundlegende Schicht für die moderne Kryptographie.
Auszeichnungen und Ehrungen
Wigderson erhielt 1994 den Nevanlinna-Preis, einen Preis der Internationalen Mathematischen Union, für seine Arbeit zur computationalen Komplexität. Im Jahr 2009 teilte er sich den Gödel-Preis für die Zickzack-Konstruktion von Graphen. Er wurde 2011 in die American Academy of Arts and Sciences gewähltund 2018 als ACM Fellow für Beiträge zur theoretischen Informatikund Mathematik..
Im Jahr 2019 erhielt Wigderson den Knuth-Preis für, unter anderem, Arbeiten zum randomisierten Rechnen, zur Schaltkreis-Komplexität, zur Beweis-Komplexitätund zum parallelen Rechnen. Er erhielt den Abel-Preis im Jahr 2021 zusammen mit László Lovász für grundlegende Beiträge zur theoretischen Informatikund diskreten Mathematik. Im April 2024 verlieh ihm die Association for Computing Machinery den Turing-Award für die Neugestaltung des Verständnisses von Zufall in der Berechnungund für jahrzehntelange Führungsrolle in der theoretischen Informatik. Ihm wurde auch die Great-Immigrant-Auszeichnung der Carnegie Corporation im Jahr 2025 verliehen.
Persönliches Leben
Wigderson ist mit Edna verheiratet, und sie haben einen Sohn, Yuval, der Professor für Mathematik am Institute of Science and Technology Austria ist. Wigderson inspiriert weiterhin aufstrebende Forscher durch seine Arbeitund Mentoring.