Ehemaliger Doktorand Robin Moser erhält renommierten Gödel-Preis
Einer der renommiertesten Preise auf dem Gebiet der theoretischen Informatik wurde Robin Moser (D-INFK) für seine algorithmische Version des Lovász-Local-Lemma verliehen.
Das Paper "A constructive proof of the general Lovász Local Lemma" wurde 2010 im Journal of the ACM 57(2): 11:1-11:15 zusammen mit dem Autor Prof. Gábor Tardos veröffentlicht.
Die Arbeit thematisiert das Lovász-Local-Lemma (LLL), ein wichtiges Werkzeug der probabilistischen Methode, welches ermöglicht, die Existenz bestimmter Objekte nachzuweisen, auch wenn sie mit exponentiell kleiner Wahrscheinlichkeit auftreten.
Der ursprüngliche Beweis war nicht algorithmisch und nachfolgende algorithmische Versionen hatten signifikante Parameterverluste. Das veröffentlichte Paper liefert ein einfaches, leistungsfähiges algorithmisches Paradigma, das fast alle bekannten Anwendungen des LLL in randomisierte Algorithmen umwandelt, die den Grenzen des Existenznachweises entsprechen. Die Arbeit bietet zusätzlich einen derandomisierten Algorithmus, einen parallelen Algorithmus und eine Erweiterung des "einseitigen" LLL.
Das neue algorithmische Paradigma beinhaltet ein Resampling von Variablen, die schlechte Ereignisse erzeugt haben. Ein solches Resampling wurde später in zahlreichen anderen Arbeiten verwendet - auch in solchen, die sich nicht direkt auf das LLL beziehen. Darüber hinaus liefert das Paper einen eleganten Beweis der Richtigkeit unter Verwendung von Zeugenbäumen. Zeugenbäume sind weit über das LLL hinaus einflussreich gewesen und haben die Methode der "entropy compression" in der Kombinatorik inspiriert. Die Stärke und Einfachheit Mosers Arbeit machen sie zu einem weitreichenden Erfolg.
Über Robin Moser
Robin Moser promovierte 2012 am Departement Informatik der ETH Zürich, wo er Mitglied der Forschungsgruppe von Prof. Emo Welzl war. Seine Dissertation beschäftigte sich mit "Exact Algorithms for Constraint Satisfaction Problems". Seine Karriere umfasste Praktika bei der Europäischen Organisation für Kernforschung (CERN) in Genf sowie bei Microsoft Research in Redmond, Washington, USA. Seit 2013 arbeitet er an der Entwicklung von Handelssoftware und als quantitativer Analyst für Circular Capital in der Region Basel in der Schweiz.
Über den Gödel-Preis
Der Gödel-Preis für herausragende Arbeiten auf dem Gebiet der theoretischen Informatik wird gemeinsam von der European Association for Theoretical Computer Science (EATCS) und der Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM SIGACT) gestiftet und jährlich verliehen. Der 28. Gödel-Preis wird im Rahmen des 47. Internationalen Kolloquiums über Roboter, Sprachen und Programmierung verliehen, welches vom 8. bis 11. Juli 2020 in Saarbrücken, Deutschland, stattfindet. Der Preis ist zu Ehren von Kurt Gödel in Anerkennung seiner bedeutenden Beiträge zur mathematischen Logik benannt.