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.