Der Turing Award 2023 ist da! Warum ist die „Zufälligkeit“ im Computer so wichtig?

Gestern Abend gab die Association for Computing Machinery (ACM) bekannt, dass der ACM AM Turing Award 2023 an den Mathematiker und führenden theoretischen Informatiker Avi Wigderson verliehen wird. In Anerkennung seiner grundlegenden Beiträge zur Computertheorie , einschließlich der Neugestaltung unseres Verständnisses der Rolle des Zufalls in der Informatik, und seiner jahrzehntelangen Führungsrolle auf dem Gebiet der theoretischen Informatik.

Der ACM AM Turing Award wurde 1966 von der ACM ins Leben gerufen, um Personen auszuzeichnen, die wichtige Beiträge zur Computerindustrie geleistet haben. Der Turing Award ist nach Alan M. Turing benannt, einem britischen Wissenschaftler und Pionier der Informatik. Einer der Zwecke der Schaffung dieses Preises besteht darin, diesen großen Wissenschaftler zu ehren.

Der Turing Award stellt extrem hohe Anforderungen an die Gewinner und unterliegt einem sehr strengen Bewertungsprozess. Im Allgemeinen wird jedes Jahr nur ein Informatiker ausgezeichnet, und nur in sehr seltenen Jahren erhalten zwei Wissenschaftler, die Beiträge in die gleiche Richtung geleistet haben, gleichzeitig den Preis. Daher ist der Turing Award auch die prestigeträchtigste und edelste Auszeichnung der Computerbranche und wird als „Nobelpreis der Computerbranche“ bezeichnet.

Was ist theoretische Informatik?

Die Theoretische Informatik beschäftigt sich mit den mathematischen Grundlagen des Faches. Es werden Fragen gestellt wie: „Ist dieses Problem rechnerisch lösbar?“ oder „Wenn dieses Problem rechnerisch gelöst werden kann, wie viel Zeit und andere Ressourcen wären erforderlich?“ Die theoretische Informatik beschäftigt sich außerdem mit dem Entwurf effizienter Algorithmen.

Jede Computertechnologie, die eng mit unserem Leben verbunden ist, wird durch Algorithmen implementiert. Wenn wir verstehen, wie leistungsstarke und effiziente Algorithmen funktionieren, vertiefen wir nicht nur unser Verständnis der Informatik, sondern auch der Naturgesetze. Forschungsdurchbrüche in der theoretischen Informatik haben den Fortschritt in nahezu allen Bereichen der Disziplin vorangetrieben, von der Kryptographie und Computerbiologie bis hin zu Netzwerkdesign, maschinellem Lernen und Quantencomputing.

Warum ist Zufälligkeit wichtig?

Computer sind grundsätzlich deterministische Systeme; Der Satz algorithmischer Anweisungen, der auf eine gegebene Eingabe angewendet wird, bestimmt eindeutig deren Berechnung und insbesondere deren Ausgabe. Mit anderen Worten: Ein deterministischer Algorithmus folgt einem vorhersehbaren Muster. Im Gegensatz dazu fehlt dem Zufall ein klares Muster oder die Vorhersagbarkeit von Ereignissen oder Ergebnissen. Da die Welt, in der wir leben, voller Zufallsereignisse wie Wettersystemen, biologischen und Quantenphänomenen ist, haben Informatiker Algorithmen so erweitert, dass sie bei Berechnungen zufällige Entscheidungen treffen und so ihre Effizienz verbessern können. Tatsächlich wurden viele Probleme, für die keine effizienten deterministischen Algorithmen bekannt sind, mithilfe probabilistischer Algorithmen effizient gelöst, wenn auch mit einer geringen Fehlerwahrscheinlichkeit (die effektiv reduziert werden kann).

Aber ist Zufälligkeit unbedingt erforderlich oder kann sie vermieden werden? Wie steht es um die Qualität der Zufälligkeit, die für den Erfolg probabilistischer Algorithmen erforderlich ist? Diese und viele andere grundlegende Fragen sind der Schlüssel zum Verständnis von Zufälligkeit und Pseudozufälligkeit in der Informatik. Ein tieferes Verständnis der Dynamik der Stochastik bei Berechnungen kann uns dabei helfen, bessere Algorithmen zu entwickeln und unser Verständnis der Natur der Berechnung selbst zu vertiefen.

Wigdersons Beitrag

Wigderson ist führend auf dem Gebiet der Komplexitätstheorie, der Algorithmen und Optimierung, des Zufallsprinzips und der Kryptografie, der parallelen und verteilten Datenverarbeitung, der Kombinatorik, der Graphentheorie und der Verbindung zwischen theoretischer Informatik und Mathematik und Naturwissenschaften.

Seit vier Jahrzehnten ist Wigderson eine führende Persönlichkeit in der theoretischen Forschung der Informatik und leistet grundlegende Beiträge zum Verständnis der Rolle von Zufälligkeit und Pseudozufälligkeit in der Informatik.

Informatiker haben einen bemerkenswerten Zusammenhang zwischen Zufälligkeit und Rechenschwierigkeit entdeckt (d. h. der Identifizierung natürlicher Probleme, für die es keine effizienten Algorithmen gibt). Wigderson hat in Zusammenarbeit mit Kollegen eine Reihe einflussreicher Bücher über den Tausch von Zufälligkeit gegen Schwierigkeit geschrieben. Sie zeigen, dass jeder probabilistische Algorithmus in polynomieller Laufzeit unter gängigen, allgemein anerkannten Rechenannahmen effizient derandomisiert (d. h. vollständig deterministisch gemacht) werden kann.

Mit anderen Worten: Zufälligkeit ist keine notwendige Voraussetzung für effizientes Rechnen. Diese Reihe von Arbeiten revolutionierte unser Verständnis der Rolle des Zufalls in der Computertechnik und veränderte unsere Denkweise über den Zufall. Zu diesen einflussreichen Arbeiten gehören die folgenden drei:

1) „Hardness vs. Randomness“ (gemeinsam mit Noam Nisan verfasst). Unter anderem stellt das Papier einen neuen Typ von Pseudozufallsgenerator vor und zeigt, dass eine effiziente deterministische Simulation von Zufallsalgorithmen unter schwächeren Annahmen als bisher bekannt möglich ist.

Link zum Artikel: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

2) „BPP verfügt über subexponentielle Zeitsimulationen, sofern EXPTIME nicht über veröffentlichbare Beweise verfügt“ (gemeinsam mit László Babai, Lance Fortnow und Noam Nisan verfasst). In diesem Artikel wird eine „Härteverstärkung“ verwendet, um zu beweisen, dass unter schwächeren Annahmen die begrenzte Fehlerwahrscheinlichkeit in polynomialer Zeit (BPP) für unendliche Eingabelängen in subexponentieller Zeit simuliert werden kann.

Link zum Artikel: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/NOAM/HARDNESS/final.pdf

3) „P = BPP, wenn E Exponentialschaltungen erfordert: Derandomisierung des XOR-Lemmas“ (gemeinsam mit Russell Impagliazzo verfasst) Dieses Dokument stellt einen stärkeren Pseudozufallsgenerator vor, der einen nahezu optimalen Kompromiss zwischen Schwierigkeit und Zufälligkeit erreicht.

Link zum Artikel: https://dl.acm.org/doi/pdf/10.1145/258533.258590

Wichtig ist, dass die Auswirkungen dieser drei Arbeiten weit über den Bereich der Zufälligkeit und Derandomisierung hinausgehen. Die Ideen in diesen Aufsätzen wurden später auf viele Bereiche der theoretischen Informatik angewendet und führten zu einflussreichen Aufsätzen mehrerer führender Persönlichkeiten auf diesem Gebiet. Später arbeitete Wigderson noch immer auf dem weiten Gebiet der computergestützten Zufallstheorie und arbeitete mit Omer Reingold, Salil Vadhan und Michael Capalbo zusammen. In einem weiteren Artikel schlug er erstmals eine effiziente kombinatorische Konstruktion erweiterter Graphen vor, bei denen es sich um dünn besetzte Graphen mit starker Konnektivität handelt. Sie haben viele wichtige Anwendungen sowohl in der Mathematik als auch in der theoretischen Informatik.

Link zum Artikel: https://www.math.ias.edu/~avi/PUBLICATIONS/MYPAPERS/CRVW01/crvw01.pdf

Neben seiner Forschung zum Thema Zufall ist Wigderson führend in mehreren Bereichen der theoretischen Informatik, darunter interaktive Beweise mit mehreren Verifizierern, Kryptografie und Schaltungskomplexität.

Respektvoller Mentor

Zusätzlich zu seinen bahnbrechenden technischen Beiträgen galt Wigderson als angesehener Mentor und Kollege, der zahllose junge Forscher beriet. Sein breites Wissen und seine hervorragenden technischen Fähigkeiten, kombiniert mit seiner Freundlichkeit, Begeisterung und Großzügigkeit, ermöglichten es ihm, viele der besten jungen Leute für das Gebiet der theoretischen Informatik zu gewinnen.

„Es ist wichtig hervorzuheben, dass Avi Wigderson auch den Abel-Preis erhielt, der als die wichtigste Auszeichnung für das Lebenswerk in der Mathematik gilt“, sagte ACM-Präsident Yannis Ioannidis. „Avi Wigdersons Arbeit über Zufälligkeit und andere Themen hat in den letzten drei Jahrzehnten die Richtung der theoretischen Informatik vorgegeben“, erklärte Jeff Dean, Senior Vice President of Research bei Google. „Seit den Anfängen der Informatik haben Forscher erkannt, dass Zufälligkeit eine Möglichkeit bietet, schnellere Algorithmen für ein breites Anwendungsspektrum zu entwickeln. Die Bemühungen, den Zufall besser zu verstehen, bringen unserem Fachgebiet weiterhin wichtige Vorteile, und Wigderson hat auf diesem Gebiet Neuland betreten.“

Wigdersons Lebenslauf

Seit 1999 ist Wigderson Herbert H. Maas-Professor für Mathematik am Institute for Advanced Study in Princeton. Zuvor war er Professor an der Hebräischen Universität Jerusalem und Gastprofessor an der Princeton University, der UC Berkeley, IBM und anderen Institutionen.

Wigderson absolvierte das Technion-Israel Institute of Technology und erhielt seinen MS, MSE und PhD in Informatik von der Princeton University. Zu seinen Auszeichnungen zählen der Abel-Preis, der IMU Abacus-Preis, der Donald E. Knuth-Preis, der Edsger W. Dijkstra-Preis für verteiltes Rechnen und der Gödel-Preis. Er ist Fellow der ACM, der National Academy of Sciences und der American Academy of Arts and Sciences.

Referenzlink: https://awards.acm.org/about/2023-turing