ACM-Turing-Preis 2023 an Professor Avi Wigderson verliehen

• Die theoretische Informatik befasst sich mit den mathematischen Grundlagen des Computing. Sie stellt Fragen wie: „Ist dieses Problem durch Computing lösbar?“ und „Wenn dieses Problem durch Computing lösbar ist, wie viel Zeit und Ressourcen werden dafür benötigt?“ Außerdem untersucht sie Methoden zum Entwurf effizienter Algorithmen. Jede Computing-Technologie, die unser Leben beeinflusst, wird durch Algorithmen möglich. Die Prinzipien leistungsfähiger und effizienter Algorithmen zu verstehen, vertieft nicht nur das Verständnis der Informatik, sondern auch das Verständnis der Naturgesetze. Die theoretische Informatik ist als Feld bekannt, das spannende intellektuelle Herausforderungen bietet, und steht oft nicht in direktem Zusammenhang mit der Verbesserung praktischer Anwendungen des Computing. Dennoch führen Forschungsinnovationen in diesem Bereich zu Fortschritten in nahezu allen Feldern, darunter Kryptografie, Computational Biology, Netzwerkdesign, Machine Learning und Quantencomputing.

• Grundsätzlich sind Computer deterministische Systeme. Wendet man die Menge der Anweisungen eines Algorithmus auf eine bestimmte Eingabe an, ist die Berechnung eindeutig festgelegt, insbesondere auch die Ausgabe. Mit anderen Worten: Deterministische Algorithmen folgen vorhersagbaren Mustern. Zufälligkeit hingegen ist durch das Fehlen klar definierter Muster oder der Vorhersagbarkeit von Ereignissen/Ergebnissen gekennzeichnet. Da die Welt, in der wir leben, voller zufälliger Ereignisse zu sein scheint — etwa Wettersysteme sowie biologische oder Quantenphänomene — haben Informatiker Algorithmen so erweitert, dass sie während des Rechenprozesses zufällige Entscheidungen treffen können, um ihre Effizienz zu steigern. Tatsächlich wurden viele Probleme, für die keine effizienten deterministischen Algorithmen bekannt sind, durch probabilistische Algorithmen effizient gelöst (mit einer kleinen Fehlerwahrscheinlichkeit, die sich jedoch effizient verringern lässt). Aber ist Zufälligkeit essenziell, oder kann sie eliminiert werden? Welche Qualität der Zufälligkeit ist für den Erfolg probabilistischer Algorithmen erforderlich?

• Avi Wigderson hat die Forschung in der theoretischen Informatik über 40 Jahre lang maßgeblich geprägt und grundlegende Beiträge zum Verständnis der Rolle von Zufälligkeit und Pseudozufälligkeit im Computing geleistet. Informatiker entdeckten bemerkenswerte Zusammenhänge zwischen Zufälligkeit und Rechenschwierigkeit, also der Identifikation natürlicher Probleme, für die es keine effizienten Algorithmen gibt. Wigderson führte gemeinsam mit Kollegen eine äußerst einflussreiche Reihe von Arbeiten darüber durch, Schwierigkeit gegen Zufälligkeit einzutauschen. Unter standardmäßigen und weithin akzeptierten Rechenannahmen bewiesen sie, dass sich bei allen probabilistischen Polynomialzeit-Algorithmen die Zufälligkeit effizient entfernen lässt, also dass sie vollständig deterministisch gemacht werden können. Anders gesagt: Zufälligkeit ist für effizientes Computing nicht essenziell. Diese Arbeiten revolutionierten unser Verständnis der Rolle von Zufälligkeit im Computing und die Art, wie wir über Zufälligkeit denken.

Wigdersons Beiträge

• "Hardness vs. Randomness" (gemeinsam mit Noam Nisan verfasst): Diese Arbeit führte unter anderem einen neuen Typ von Pseudozufallszahlengenerator ein und bewies, dass eine effiziente deterministische Simulation randomisierter Algorithmen unter deutlich schwächeren Annahmen möglich ist als zuvor bekannt.

• "BPP Has Subexponential Time Simulations Unless EXPTIME has Publishable Proofs" (gemeinsam mit László Babai, Lance Fortnow und Noam Nisan verfasst): Diese Arbeit zeigte unter Verwendung von „hardness amplification“, dass bounded-error probabilistic polynomial time (BPP) unter schwächeren Annahmen für unendlich viele Eingabelängen in subexponential time simuliert werden kann.

• "P = BPP if E Requires Exponential Circuits: Derandomizing the XOR Lemma" (gemeinsam mit Russell Impagliazzo verfasst): Diese Arbeit stellte einen stärkeren Pseudozufallszahlengenerator mit einem im Wesentlichen optimalen Hardness-vs.-Randomness-Trade-off vor.

• Über seine Forschung zu Zufälligkeit hinaus hat Wigderson auch in mehreren anderen Bereichen der theoretischen Informatik intellektuelle Führungsstärke gezeigt, darunter interaktive Beweise mit mehreren Beweisführern, Kryptografie und Schaltkreis-Komplexität.

Meinung von GN⁺

• Wigdersons Forschung, die aus mathematischer Sicht die Beziehung zwischen Zufälligkeit und Rechenkomplexität nachgewiesen hat, ist von großer Bedeutung im Hinblick auf die Verbindung von Informatik und Mathematik. Insbesondere der Nachweis, dass viele Algorithmen, die von Zufälligkeit abhängig zu sein schienen, tatsächlich deterministisch in gleicher Weise implementiert werden können, wird als Eröffnung eines neuen Horizonts in der Informatik bewertet.

• Auch der mathematische Zugang zur Beziehung zwischen Effizienz und Schwierigkeit dürfte ein wichtiges Forschungsthema der theoretischen Informatik bleiben. Die Einsicht, dass bei schwierigeren Problemen proportional dazu die Möglichkeit effizienterer Algorithmen bestehen könnte, ist eine kontraintuitive Erkenntnis.

• Dass Professor Wigderson sich zudem für die Weiterentwicklung der theoretischen Informatik einsetzte, die Verbindung von Mathematik und Informatik betonte und sich der Förderung des wissenschaftlichen Nachwuchses widmete, dürfte ein gutes Vorbild für kommende Generationen in der Wissenschaft sein. Besonders seine Auszeichnung sowohl mit dem Abel-Preis der Mathematik als auch mit dem Turing-Preis der Informatik ist ein symbolträchtiges Beispiel für die Bedeutung der theoretischen Informatik.

[GN⁺]

Hacker-News-Kommentar

• Avi Wigderson wurde mit dem ACM A.M. Turing Award 2023 ausgezeichnet. Gewürdigt wurden seine grundlegenden Beiträge zur Berechnungstheorie, insbesondere dafür, dass er das Verständnis der Rolle von Zufälligkeit in Berechnungen neu geprägt hat, sowie seine über Jahrzehnte ausgeübte intellektuelle Führungsrolle in der theoretischen Informatik.

• Wigderson war eine führende Persönlichkeit in Bereichen wie der Theorie der Berechnungskomplexität, Algorithmen und Optimierung, Zufälligkeit und Kryptografie, parallelem und verteiltem Rechnen, Kombinatorik und Graphentheorie und fungierte zudem als Bindeglied zwischen theoretischer Informatik sowie Mathematik und Naturwissenschaften.

• Eine von Wigdersons wichtigsten Leistungen ist die Entdeckung der bemerkenswerten Verbindung zwischen Zufälligkeit und rechnerischer Schwierigkeit. Seine Forschung zeigte, dass Zufälligkeit für effiziente Berechnungen nicht zwingend erforderlich ist.

• 2021 erhielt er zudem den Abel-Preis und hat damit die seltene Auszeichnung, die höchsten Ehrungen sowohl in der theoretischen/abstrakten Mathematik als auch in der Informatik erhalten zu haben.

• Sein Buch "Mathematics and Computation" ist vor Kurzem erschienen und wird sehr positiv aufgenommen.

• Seinen Forschungsergebnissen zufolge ist, wenn eine Aussage beweisbar ist, auch ein Zero-Knowledge-Proof dafür möglich; und wenn man Pseudozufallszahlen auf probabilistische Algorithmen anwendet, kann man effiziente deterministische Algorithmen für dasselbe Problem erhalten. Das deutet darauf hin, dass sich die Komplexität probabilistischer Rechenmodelle wie in der KI stark verringern lässt.