Avi Wigderson

Avi Wigderson (* 9. September 1956) ist ein israelischer Mathematiker und Informatiker. 2021 wurde ihm der Abelpreis mit László Lovász zugesprochen. Beide erhielten ihn für ihre grundlegenden Beiträge zur theoretischen Informatik und zur diskreten Mathematik und für ihre führende Rolle bei deren Entwicklung zu zentralen Gebieten der modernen Mathematik.^[1] 2024 erhielt Wigderson mit dem Turing Award die wohl bedeutendste Auszeichnung der Informatik.

Wigderson wuchs in Haifa als einer von drei Söhnen von Holocaust-Überlebenden auf. Sein Vater war Elektroingenieur und weckte in ihm die Liebe zu Puzzles. Nach eigenen Worten verbrachte er seine Jugend zum Teil am Strand, zum Teil als typischer Nerd.^[2] Er studierte von 1977 bis 1980 Informatik am Technion in Haifa, Israel und erhielt dort seinen Bachelor of Science (Summa cum laude). Im Rückblick lobte er die theoretische Ausrichtung des Informatikstudiums in Israel, der die Rolle der Mathematik betonte und wertschätzte, im Gegensatz zu einer mehr praktischen Ausrichtung in den USA.^[2] Anschließend besuchte er von 1980 bis 1983 die Princeton University in den Vereinigten Staaten, wo er seinen Master-Abschluss in Informatik erhielt und bei Richard J. Lipton promovierte (Studies in computational complexity).^[3] Als Post-Doktorand war er an der University of California, Berkeley, am IBM Almaden Research Center in San José und am MSRI (1985/86).^[4] Ab 1986 lehrte er an der Hebräischen Universität in Jerusalem, zuletzt mit voller Professur. Seit 1999 ist er außerdem Professor am Institute for Advanced Study, an dem er seit 2003 in Vollzeit ist (permanent residence, außerdem Herbert H. Maass Professor). Seine Stelle an der Hebräischen Universität gab er dafür auf.

1990 bis 1992 war er Gastwissenschaftler an der Princeton University und 1995/96 am Institute for Advanced Study.^[4]

Avi Wigderson untersucht in der Komplexitätstheorie Probleme an den Grenzen oder jenseits der Leistungsfähigkeit selbst der stärksten Computer und solch schweren Problemen, für die bisher keine effizienten Algorithmen bekannt sind, und das Zusammenspiel von Berechenbarkeit und Zufallsmethoden mit Anwendungen zum Beispiel in der Kryptographie und Sicherheit von Rechnernetzwerken und elektronischer Kommunikation.

Er forschte unter anderem über Expander-Graphen,^[5] Interaktive Beweissysteme^[6] bzw. Zero-Knowledge-Beweissysteme.

1992 bewies er mit Ran Raz, dass das Perfect-Matching-Problem für Berechnung mit monotonen Schaltkreisen (also solchen nur mit AND und OR-Gatter, ohne NOT) linear in der Anzahl der Knoten des Graphen ist. Es gibt auf solchen Schaltkreisen also prinzipiell keine gute Methode dieses Problem zu lösen. Das zeigte einen bedeutenden Unterschied von monotonen zu nicht-monotonen Schaltkreisen.^[7] Ebenfalls Anfang der 1990er Jahre begann er den Einfluss von Zufallsentscheidungen auf die Berechenbarkeit zu untersuchen. Den Vorteil der Verwendung von Zufallsprozessen bei Berechnungen hatten Informatiker in der Praxis schon in den 1970er Jahren entdeckt und es schien Anfang der 1990er Jahre so, als ob man bei fast allen Problemen damit schneller vorankäme. Dann zeigte Wigderson mit Russell Impagliazzo, dass unter bestimmten Bedingungen schnelle Zufallsalgorithmen immer in deterministische Algorithmen umgewandelt werden können: die Komplexitätsklasse BPP ist unter einer häufig als zutreffend angenommenen Voraussetzung gleich der Komplexitätsklasse P.^[8] Die Voraussetzung ist, dass die Komplexitätsklasse E exponentielle Schaltkreiskomplexität hat. Ihr Resultat beruht auf der Möglichkeit der Konstruktion geeigneter Pseudozufallsgeneratoren, ordnete zufällige Algorithmen in die Hierarchie der Komplexitätsklassen ein und änderte die Denkweise der Informatiker über Zufallsalgorithmen grundlegend. Nach Wigdersons eigener Einschätzung setzte sich damit die Erkenntnis durch, dass Zufallsalgorithmen eher schwach sind statt starke Algorithmen, da unter der erwähnten Voraussetzung die Zufälligkeit eliminiert werden kann.^[1]

Zu seinen Errungenschaften in der Komplexitätstheorie gehört auch das Zig-zag-Produkt. Es fand vielfache Anwendung und dient zum Beispiel dafür einen Weg aus einem Labyrinth zu finden auf Basis nur einer endlichen Anzahl von Kreuzungen.^[1]

Von ihm stammen über 200 wissenschaftliche Aufsätze und er betreute über 100 Post-Doktoranden am IAS und an der Hebräischen Universität (Stand 2021).^[2] Zu seinen Doktoranden zählen Ran Raz, Prabhakar Ragde (University of Waterloo) und Dorit Aharonov.

1994 wurde ihm der Nevanlinna-Preis für seine Arbeit auf dem Gebiet der Komplexitätstheorie verliehen, der höchste Preis für Beiträge aus der Informatik der Internationalen Mathematischen Union, die auf den Internationalen Mathematikerkongressen verliehen wird. 2006 hielt er einen Plenarvortrag auf dem Internationalen Mathematikerkongress in Madrid (P, NP and mathematics: a computational complexity perspective) und 1990 war er Invited Speaker auf dem ICM in Kyōto (Information theoretic reasons for computational difficulty). Im Jahr 2008 erhielt er den Levi-L.-Conant-Preis und 2009 folgte der Gödel-Preis (mit Omer Reingold, Salil Vadhan für ihre Arbeit zum zig-zag Produkt von Graphen), 2008 hielt er die Gibbs Lecture, 2019 erhielt er den Knuth-Preis. 2011 wurde er in die American Academy of Arts and Sciences gewählt, 2013 in die National Academy of Sciences, seit 2018 ist er Fellow der Association for Computing Machinery. 2018 hielt er die Colloquium Lectures der American Mathematical Society (Titel: 1) Alternate Minimization and Scaling algorithms: theory, applications and connections across mathematics and computer science; 2) Proving algebraic identities; 3) Proving analytic inequalities). 2021 erhielt er den Abelpreis, eine der höchsten mathematischen Auszeichnungen. 2022 hielt er einen Plenarvortrag auf dem Internationalen Mathematikerkongress (Symmetry, computations and math (or: can ${\displaystyle P\neq NP}$ be proved via gradient descent ?)).

2024 wurde Wigderson der Turing Award (des Jahres 2023) „für grundlegende Beiträge zur Berechnungstheorie, einschließlich der Neugestaltung unseres Verständnisses der Rolle des Zufalls in der Berechnung, und für seine jahrzehntelange intellektuelle Führung in der theoretischen Informatik“ zugesprochen.^[9]

Wigderson ist verheiratet und hat drei Kinder.

• Mathematics and Computation. A Theory Revolutionizing Technology and Science. Princeton University Press, 2019. (Online verfügbar via IAS.edu)

Commons: Avi Wigderson – Sammlung von Bildern, Videos und Audiodateien

• Homepage am IAS
• Avi Wigderson and the Second Golden Era of Theoretical Computing, IAS (zum Abelpreis 2021)

1. ↑ ^{a b c} Kevin Hartnett, Pioneers Linking Math and Computer Science Win the Abel Prize, Quanta Magazine, 17. März 2021
2. ↑ ^{a b c} Avi Wigderson and the Second Golden Era of Theoretical Computing, IAS, Porträt zum Abelpreis 2021.
3. ↑ Avi Wigderson im Mathematics Genealogy Project (englisch) Vorlage:MathGenealogyProject/Wartung/id verwendet
4. ↑ ^{a b} CV von Wigderson von 2010, [1] (pdf) in der waybackmachine.
5. ↑ Shlomo Hoory, Nathan Linial, Avi Wigderson: Expander Graphs and their Applications, Bulletin of the AMS, Band 43, 2006, S. 439–561.
6. ↑ Oded Goldreich, Silvio Micali, Avi Wigderson: Proofs that yield nothing but their validity, Journal of the ACM, Band 38, 1991, S. 690–728. Sie zeigten 1987 die Existenz eines sicheren Protokolls für jedes Vielparteien-Kommunikationsproblem (Secure Multiparty Computation) unter Verwendung von Zero Knowledge-Beweisen.
7. ↑ Raz, Wigderson, Monotone circuits for matching require linear depth, Journal of the ACM, Band 39, 1992, S. 736–744, Abstract
8. ↑ R. Impagliazzo, A. Wigderson: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: 29th STOC, 1997, S. 220–229
9. ↑ ACM A.M. Turing Award Honors Avi Wigderson for Foundational Contributions to the Theory of Computation abgerufen am 29. April 2024.