imported>Dandelo: typo

2026-02-24T21:36:30Z

typo

Neue Seite

[[Datei:Avi Wigderson (London 2012).jpg|mini|Avi Wigderson, London 2012]]
'''Avi Wigderson''' (* [[9. September]] [[1956]]) ist ein [[israel]]ischer [[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“.<ref name="quanta">[https://www.quantamagazine.org/avi-wigderson-and-laszlo-lovasz-win-abel-prize-20210317/ Kevin Hartnett, Pioneers Linking Math and Computer Science Win the Abel Prize], Quanta Magazine, 17. März 2021</ref> 2024 erhielt Wigderson mit dem [[Turing Award]] die bedeutendste Auszeichnung der Informatik.

== Leben ==
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 kniffligen Rätseln. Nach eigenen Worten verbrachte er seine Jugend zum Teil am Strand, zum Teil als typischer Nerd.<ref name="ias">[https://www.ias.edu/ideas/avi-wigderson-and-second-golden-era-theoretical-computing Avi Wigderson and the Second Golden Era of Theoretical Computing], IAS, Porträt zum Abelpreis 2021.</ref> Er studierte von 1977 bis 1980 [[Informatik]] am [[Technion]] in [[Haifa]], [[Israel]] und erhielt dort seinen [[Bachelor|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.<ref name="ias"/> Anschließend besuchte er von 1980 bis 1983 die [[Princeton University]] in den [[Vereinigte Staaten|Vereinigten Staaten]], wo er seinen [[Master]] in Informatik erhielt und bei [[Richard J. Lipton]] [[Promotion (Doktor)|promovierte]] (''Studies in computational complexity'').<ref>{{MathGenealogyProject|id=82100}}</ref> Als [[Post-Doktorand]] war er an der [[University of California, Berkeley]], am [[IBM Almaden Research Center]] in [[San José (Kalifornien)|San José]] und am [[MSRI]] (1985/86).<ref name="CV">CV von Wigderson von 2010, [https://web.archive.org/web/20100612023406/http://math.ias.edu/~avi/cv%20%26%20short%20bio/shortbio.pdf%7Carchiviert] (pdf) in der waybackmachine.</ref> Ab 1986 lehrte er an der [[Hebräische Universität|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.<ref name="CV"/>

== Werk ==
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-Graph]]en,<ref>Shlomo Hoory, Nathan Linial, Avi Wigderson: Expander Graphs and their Applications, Bulletin of the AMS, Band 43, 2006, S. 439–561.</ref> [[Interaktives Beweissystem|Interaktive Beweissysteme]]<ref>[[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.</ref> bzw. [[Zero-Knowledge-Beweis|Zero-Knowledge-Beweissysteme]].

1992 bewies er mit [[Ran Raz]], dass das [[Matching (Graphentheorie)|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.<ref>Raz, Wigderson, Monotone circuits for matching require linear depth, Journal of the ACM, Band 39, 1992, S. 736–744, [https://dl.acm.org/doi/10.1145/146637.146684 Abstract]</ref> 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 (Komplexitätsklasse)|BPP]] ist unter einer häufig als zutreffend angenommenen Voraussetzung gleich der Komplexitätsklasse [[P (Komplexitätsklasse)|P]].<ref>R. Impagliazzo, A. Wigderson: P=BPP if E requires exponential circuits: Derandomizing the XOR Lemma. In: 29th STOC, 1997, S. 220–229</ref> Die Voraussetzung ist, dass die Komplexitätsklasse [[E (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.<ref name="quanta"/>

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.<ref name="quanta"/>

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).<ref name="ias"/> Zu seinen Doktoranden zählen [[Ran Raz]], [[Prabhakar Ragde]] (University of Waterloo) und [[Dorit Aharonov]].

== Auszeichnungen und Mitgliedschaften ==
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 [[Internationaler Mathematikerkongress|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 (AMS)|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 <math>P \neq NP</math> 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.<ref>[https://awards.acm.org/about/2023-turing ''ACM A.M. Turing Award Honors Avi Wigderson for Foundational Contributions to the Theory of Computation''] abgerufen am 29. April 2024.</ref>

== Privates ==
Wigderson ist verheiratet und hat drei Kinder.

== Schriften (Auswahl) ==
* ''Mathematics and Computation. A Theory Revolutionizing Technology and Science''. Princeton University Press, 2019. (Online verfügbar via [https://www.math.ias.edu/files/Book-online-Aug0619.pdf#page=1 IAS.edu])

== Weblinks ==
{{commonscat}}
* {{MacTutor|id=Wigderson}}
* [http://www.math.ias.edu/~avi Homepage am IAS]
* [https://www.ias.edu/ideas/avi-wigderson-and-second-golden-era-theoretical-computing Avi Wigderson and the Second Golden Era of Theoretical Computing], IAS (zum Abelpreis 2021)
* [https://zbmath.org/authors/wigderson.avi Avi Wigderson] in der Datenbank [[zbMATH]]

== Einzelnachweise ==
<references />

{{Navigationsleiste Träger des Levi-L.-Conant-Preises}}
{{Navigationsleiste Träger des Abelpreises}}
{{Navigationsleiste Träger des Turing-Awards}}

{{Normdaten|TYP=p|GND=170069257|LCCN=n89624795|VIAF=216256855}}

{{SORTIERUNG:Wigderson, Avi}}
[[Kategorie:Mathematiker (20. Jahrhundert)]]
[[Kategorie:Informatiker]]
[[Kategorie:Absolvent der Princeton University]]
[[Kategorie:Hochschullehrer (Institute for Advanced Study)]]
[[Kategorie:Hochschullehrer (Hebräische Universität Jerusalem)]]
[[Kategorie:Mitglied der American Academy of Arts and Sciences]]
[[Kategorie:Mitglied der National Academy of Sciences]]
[[Kategorie:Träger des Abelpreises]]
[[Kategorie:Träger des Turing Award]]
[[Kategorie:Israeli]]
[[Kategorie:Geboren 1956]]
[[Kategorie:Mann]]
{{Personendaten
|NAME=Wigderson, Avi
|ALTERNATIVNAMEN=
|KURZBESCHREIBUNG=israelischer Mathematiker und Informatiker
|GEBURTSDATUM=9. September 1956
|GEBURTSORT=
|STERBEDATUM=
|STERBEORT=
}}

Avi Wigderson - Versionsgeschichte

imported>Dandelo: typo