ACM-Turing-Preis 2023 an Professor Avi Wigderson verliehen

 (awards.acm.org)
1 Punkte von GN⁺ 2024-04-12 | 1 Kommentare | Auf WhatsApp teilen
  • ACM hat Avi Wigderson als Preisträger des ACM A.M. Turing Award 2023 ausgewählt und würdigt damit seine Verdienste darum, das Verständnis der Berechnungstheorie und der Rolle des Zufalls in der Berechnung neu geprägt zu haben
  • Wigderson ist Herbert H. Maass Professor am Institute for Advanced Study und eine prägende Persönlichkeit in der Theorie der Berechnungskomplexität sowie in Algorithmen, Kryptografie, parallelem und verteiltem Rechnen, Kombinatorik und Graphentheorie
  • Zu seinen zentralen Leistungen zählt die Forschung zu hardness for randomness, die zeigte, dass sich probabilistische Polynomialzeit-Algorithmen unter weithin akzeptierten Rechenannahmen deterministisch simulieren lassen
  • Die zugehörigen Arbeiten stellten Pseudorandom-Generatoren, teilsubexponentielle Zeitsimulationen für BPP und den hardness-vs-randomness-Kompromiss vor und beeinflussten zahlreiche Bereiche der theoretischen Informatik
  • Der Turing Award ist mit 1 Million US-Dollar Preisgeld dotiert, finanziert von Google, und Wigderson wird nicht nur für technische Leistungen, sondern auch als Mentor für junge Forschende gewürdigt

Hintergrund zur Verleihung des ACM Turing Award

  • ACM hat Avi Wigderson als Gewinner des ACM A.M. Turing Award 2023 ausgewählt
  • Begründet wurde die Auszeichnung mit grundlegenden Beiträgen zur Berechnungstheorie, Leistungen, die das Verständnis der Rolle von Zufall in der Berechnung neu strukturiert haben, sowie mit jahrzehntelanger intellektueller Führungsstärke in der theoretischen Informatik
  • Wigderson ist Herbert H. Maass Professor in der Fakultät für Mathematik am Institute for Advanced Study in Princeton, New Jersey

  • Zentrale Tätigkeitsfelder

    • Theorie der Berechnungskomplexität
    • Algorithmen und Optimierung
    • Zufall und Kryptografie
    • Paralleles und verteiltes Rechnen
    • Kombinatorik und Graphentheorie
    • Verbindungen zwischen theoretischer Informatik sowie Mathematik und Naturwissenschaften
    • Der ACM A.M. Turing Award wird als „Nobelpreis der Informatik“ bezeichnet und ist dank finanzieller Unterstützung von Google, Inc. mit 1 Million US-Dollar dotiert
    • Der Preis ist nach dem britischen Mathematiker Alan M. Turing benannt, der die mathematischen Grundlagen des Computings mitbegründete

Welche Fragen die theoretische Informatik behandelt

  • Theoretische Informatik beschäftigt sich mit den mathematischen Grundlagen der Informatik und mit Fragen wie: „Lässt sich dieses Problem berechnen?“ und „Falls ja, wie viel Zeit und Ressourcen werden dafür benötigt?“
  • Das Fachgebiet untersucht auch Prinzipien für den Entwurf effizienter Algorithmen
  • Algorithmen sind die Grundlage, die die im Alltag genutzten Computing-Technologien erst möglich macht
  • Die theoretische Informatik befasst sich auch mit intellektuellen Herausforderungen, die nicht sofort praktische Anwendungen verbessern, doch Forschungsdurchbrüche können Fortschritte in vielen Bereichen auslösen
    • Kryptografie
    • Computerbiologie
    • Netzwerkdesign
    • Maschinelles Lernen
    • Quantencomputing

Warum Zufall in der Berechnung wichtig ist

  • Computer sind im Kern deterministische Systeme, bei denen für eine gegebene Eingabe die Befehlsfolge eines Algorithmus die Berechnung und Ausgabe eindeutig bestimmt
  • Zufall bezeichnet einen Zustand, in dem bei Ereignissen oder Ergebnissen kein klares Muster oder keine Vorhersagbarkeit erkennbar ist
  • In der realen Welt gibt es viele Ereignisse, die zufällig erscheinen, etwa Wettersysteme, biologische Phänomene oder Quantenphänomene
  • Informatiker haben Algorithmen erweitert, damit diese während der Berechnung zufällige Entscheidungen treffen können, um die Effizienz zu steigern
  • Viele Probleme, für die kein effizienter deterministischer Algorithmus bekannt war, lassen sich mit probabilistischen Algorithmen mit kleiner Fehlerwahrscheinlichkeit effizient lösen
    • Diese Fehlerwahrscheinlichkeit lässt sich effizient verringern
  • Die zentrale Frage ist, ob Zufall unverzichtbar ist, ob er entfernt werden kann und welche Qualität von Zufall für den Erfolg probabilistischer Algorithmen erforderlich ist
  • Ein besseres Verständnis von Zufall und Pseudozufall in der Berechnung kann zu besseren Algorithmen und zu einem tieferen Verständnis des Wesens der Berechnung selbst führen

Wigdersons zentrale Forschungsbeiträge

  • Wigderson gehört seit 40 Jahren zu den prägenden Forschern der theoretischen Informatik und leistete grundlegende Beiträge zum Verständnis der Rolle von Zufall und Pseudozufall in der Berechnung
  • Informatiker entdeckten eine wichtige Verbindung zwischen Zufall und Rechenschwierigkeit, also der Identifikation natürlicher Probleme, für die es keine effizienten Algorithmen gibt
  • Wigderson und seine Co-Autoren veröffentlichten einflussreiche Arbeiten zu hardness for randomness
  • Diese Arbeiten zeigten, dass sich unter standardmäßigen und weithin akzeptierten Rechenannahmen alle probabilistischen Polynomialzeit-Algorithmen effizient deterministisch machen lassen
  • Das Ergebnis deutet darauf hin, dass Zufall für effiziente Berechnung möglicherweise nicht zwingend erforderlich ist
  • Diese Forschungslinie veränderte die Sicht auf die Rolle des Zufalls in der Berechnung und die Denkweise über Zufall grundlegend

  • Drei repräsentative Arbeiten

Wirkungsbereich und weitere Leistungen

  • Wigdersons drei Arbeiten beeinflussten viele Bereiche der theoretischen Informatik weit über Zufall und Derandomisierung hinaus
  • Die Ideen aus diesen Arbeiten wurden später in einflussreichen Publikationen vieler bedeutender Forschender aufgegriffen
  • In einer Arbeit mit Omer Reingold, Salil Vadhan und Michael Capalbo stellte er die erste effiziente kombinatorische Konstruktion von Expander-Graphen vor
    • Expander-Graphen sind dünn besetzte Graphen mit starken Konnektivitätseigenschaften
    • Sie haben wichtige Anwendungen sowohl in der Mathematik als auch in der theoretischen Informatik
  • Neben dem Thema Zufall zeigte Wigderson auch intellektuelle Führungsstärke in folgenden Bereichen
    • multi-prover interactive proofs
    • Kryptografie
    • Schaltkreis-Komplexität

Mentoring und Würdigung

  • Wigderson gilt nicht nur wegen seiner bahnbrechenden technischen Beiträge als hochgeschätzter Mentor, sondern auch als Kollege, der viele junge Forschende angeleitet hat
  • Sein enormes Wissen, seine technische Stärke, seine Nahbarkeit, seine Begeisterung und seine Großzügigkeit werden als Gründe genannt, warum viele herausragende junge Forschende eine Karriere in der theoretischen Informatik einschlugen
  • ACM-Präsident Yannis Ioannidis erklärte, Wigderson habe auch den Abel Prize erhalten, der als eine der höchsten Auszeichnungen für das Lebenswerk in der Mathematik gilt
  • Ioannidis bewertete Mathematik als Grundlage der Informatik und hob hervor, dass Wigdersons Arbeit verschiedene mathematische Teilgebiete mit der theoretischen Informatik verbunden habe
  • Google Senior Vice President Jeff Dean erklärte, Wigdersons Forschung zu Zufall und anderen Themen habe in den vergangenen 30 Jahren die Agenda der theoretischen Informatik geprägt
  • Dean betonte zudem, dass Wigderson als Mentor Ideen und Forschungsrichtungen geprägt und junge Forschende motiviert habe, in diesen Richtungen zu arbeiten

Turing Award und weitere wichtige Arbeiten von Wigderson

Verwandte Beiträge

1 Kommentare

 
GN⁺ 2024-04-12
Hacker-News-Kommentare

  • Die beiden in der Ankündigung erwähnten wichtigsten Arbeiten von Wigderson sind gemeinsam mit Noam Nisan verfasst, einem der Professoren hinter der bekannten Online-Vorlesung From Nand to Tetris

    • Professor Nisan ist ebenfalls eine beeindruckende Persönlichkeit. Nachdem er in der Berechnungstheorie erstklassige Ergebnisse erzielt hatte, hinterließ er auch in einem ziemlich anderen Gebiet, der algorithmischen Spieltheorie, großen Einfluss
      Es ist schön zu sehen, dass eine Person so vielfältige Leistungen vollbringen kann, und ebenso beeindruckend ist ein System, das eine solche Flexibilität zulässt
    • Es gibt auch ein Buch. Kürzlich ist die 2. Auflage erschienen

  • Es gibt auch einen guten Artikel von Quanta: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    Interessant war, wie viele verschiedene Posen man Wigderson hat einnehmen lassen. Es wirkt so unbeholfen. So nach dem Motto: „Setzen Sie sich bitte auf diesen Stuhl und blicken Sie versonnen aus dem Fenster“

    • Spannend fand ich die Stelle, dass die „unvernünftige Wirksamkeit des Zufalls“ Wigderson dazu brachte, über das Wesen des Zufalls selbst nachzudenken
      Ich verstehe Komplexitätsklassen als etwas, das Worst-Case-Performance behandelt, und würde gern grob verstehen, wie man beweist, dass selbst bei einem guten Pseudozufallszahlengenerator und guten randomisierten Algorithmen keine Kombination aus RNG + seed + problem instance exponentielle Zeit benötigt
    • In der Korrektur heißt es, der ursprüngliche Artikel habe angegeben, Wigderson habe die University of Haifa besucht; tatsächlich habe er aber am Technion in Haifa, Israel, studiert
      Ich frage mich, wie der Reporter das verwechseln konnte
    • Die Pose „auf einem Stuhl sitzen und aus dem Fenster schauen“ wirkt wie etwas von Martin Scorsese oder aus Sopranos. Eine Szene mit einem alten Gangster im Pflegeheim

  • Scott Aaronson hat einen Beitrag darüber geschrieben, wie ein Vortrag von Avi Wigderson seine eigene Laufbahn beeinflusst hat: https://scottaaronson.blog/?p=2925

  • In „Israeli Wins Turing Prize, Computing's Highest Honor, for Insights on Randomness“ gibt es weitere Informationen: [1] sowie eine archivierte Version [2]
    [1] https://www.haaretz.com/israel-news/2024-04-10/ty-article/.p...
    [2] https://archive.is/e8uix

  • Ich frage mich, wo man am besten anfängt, wenn man bei Wigdersons Forschung zum Trade-off zwischen Härte und Zufall aufschließen möchte
    Es kommt nicht oft vor, dass ich von einem Turing-Award-Preisträger noch nie gehört habe, aber diese Person war komplett außerhalb meines Blickfelds

    • Schau in sein Buch: https://www.math.ias.edu/avi/book
    • Ich frage mich, was mit „standardmäßigen und weithin geglaubten Berechnungsannahmen“ gemeint ist
      Vermutlich heißt es, dass auch probabilistische Approximation für NP-vollständige Probleme nicht in Polynomialzeit möglich ist; oder ich bin unsicher, ob die derandomisierte Version immer noch ein Approximationsalgorithmus ist

  • Ich habe gerade Wigdersons Buch zur Hand genommen, und bisher gefällt es mir: https://press.princeton.edu/books/hardcover/9780691189130/ma...

    • Für persönliche Forschung und Lehre kann man den finalen Entwurf des Buchs hier einsehen: https://www.math.ias.edu/avi/book
    • Ich habe in das Buch geschaut, und es scheint eher auf Doktoranden oder fortgeschrittene Bachelor-Studierende ausgerichtet zu sein
      Ich frage mich, ob jemand ein Buch empfehlen kann, das Berechnungsthemen grundlegender behandelt, für jemanden, dessen Informatik-/Mathe-Grundlagen aus dem Studium etwas eingerostet sind

  • In einem verwandten Artikel steht dieser Satz: https://www.quantamagazine.org/avi-wigderson-complexity-theo...
    „Wenn eine Aussage beweisbar ist, dann besitzt sie auch einen Zero-Knowledge-Beweis“ – das fühlt sich an, als würde einem der Kopf platzen
    Auch „Wenn man einem probabilistischen Algorithmus statt zufälliger Bits Pseudozufallsbits zuführt, erhält man einen effizienten deterministischen Algorithmus für dasselbe Problem“ ist absurd verblüffend
    Da KI ebenfalls probabilistische Berechnung ist, frage ich mich, ob das – wenn ich es richtig lese – bedeutet, dass man die Komplexität heutiger Modelle um mehrere Größenordnungen reduzieren könnte. Wenn das ein Anfängerirrtum ist, möge mich bitte jemand daraus befreien

    • Ich weiß nicht genau, was damit gemeint ist, aber das jedenfalls nicht. KI nutzt bereits Pseudozufall und ist deterministisch
      Ausnahmen gibt es, etwa spezielle KI-Beschleunigerchips, die zur Effizienzsteigerung analoge Berechnung verwenden
    • Leider nein. Erstens gilt das Ergebnis für Entscheidungsprobleme, nicht für Suchprobleme
      Zweitens ist der konstruierte deterministische Algorithmus deutlich weniger effizient als der randomisierte Algorithmus. Er gehört unter schwachen Annahmen lediglich zur gleichen Komplexitätsklasse

  • Mir gefiel diese Passage im Artikel: „Anwendungen sind nicht die Motivation, aber man weiß, dass auch Grundlagenforschung nützlich werden kann. Denken Sie an Alan Turing. Er schrieb einen mathematischen Logikaufsatz über das Entscheidungsproblem in einer wenig bekannten Zeitschrift. Anwendungen waren nicht seine Motivation“
    Das erinnert an Feynmans Teller-Anekdote. Es begann mit einer beiläufigen Reaktion auf etwas, das er in der Mensa sah, und führte am Ende zum Nobelpreis
    Allgemeiner gesagt: Die moderne Wissenschaft bewegt sich in eine Richtung, die genau solche neugiergetriebene Forschung unterdrückt

  • Laut ACM wurde Avi Wigderson für grundlegende Beiträge zur Berechnungstheorie ausgewählt, darunter die Neuformung unseres Verständnisses der Rolle von Zufall in der Berechnung, sowie für jahrzehntelange intellektuelle Führungsrolle in der theoretischen Informatik, und erhält den ACM A.M. Turing Award 2023
    Wigderson ist Herbert H. Maass Professor in der Fakultät für Mathematik am Institute for Advanced Study in Princeton, New Jersey, und war eine zentrale Figur in der Komplexitätstheorie, bei Algorithmen und Optimierung, Zufall und Kryptographie, parallelem und verteiltem Rechnen, Kombinatorik, Graphentheorie sowie an den Schnittstellen der theoretischen Informatik mit Mathematik und Naturwissenschaften
    2021 erhielt er auch den Abelpreis, was eine ziemlich ungewöhnliche Kombination aus höchsten Auszeichnungen der theoretischen/abstrakten Mathematik und der Informatik ergibt

    • Die Überschneidung zwischen theoretischer Informatik und Mathematik ist viel größer, als die meisten wissen
      Als einfaches Beispiel kann man in der MIT-Kursliste für theoretische Informatik https://catalog.mit.edu/subjects/6/ sehen, wie viele Kurse gemeinsam mit Course 18, der Mathematik, angeboten werden
    • Streng genommen ist die höchste Auszeichnung in der Mathematik die Fields Medal
      Natürlich bin ich nicht in der Position, da große Töne zu spucken

  • Ich würde mich über Empfehlungen für Materialien zum Thema Wahrscheinlichkeit/Zufall und Berechnung freuen, von einsteigerfreundlich bis fortgeschritten
    Bei Google findet man Eli Upfal und Michael Mitzenmachers „Probability and Computing: Randomization and Probabilistic Techniques in Algorithms and Data Analysis“, aber ich finde nicht recht Bücher, Texte oder Videos für Anfänger bzw. Einsteiger