Robin A. Moser

Robin Alexander Moser (* 14. August 1983; heimatberechtigt in Inkwil) ist ein Schweizer Informatiker, der sich mit kombinatorischen Algorithmen und dem SAT-Problem befasst.

Moser promovierte 2012 an der ETH Zürich bei Emo Welzl. Für seine Dissertation (Exact Algorithms for Constraint Satisfaction Problems) erhielt er den Preis für die beste Dissertation im deutschsprachigen Raum von der Gesellschaft für Informatik. In seiner Dissertation geht es um das Lovász-Local-Lemma (LLL, 1975), das starke Kriterien für die Erfüllbarkeit von Problemen mit Einschränkungen (SAT, Constraint Satisfaction) wie etwa bei Formeln der Aussagenlogik an die Hand gibt. Es dient im Rahmen probabilistischer Methoden dem Nachweis von Objekten, auch wenn sie sehr unwahrscheinlich sind. Moser entwickelte einen überraschend einfachen konstruktiven (algorithmischen) Beweis des Lemmas (der ursprüngliche Beweis war nicht-konstruktiv)., bald darauf mit Gábor Tardos ausgebaut. Ihre Arbeit ermöglichte die Umwandlung fast aller bekannten Anwendungen von LLL in randomisierte Algorithmen mit einem Resampling von Variablen, die schlechte Ergebnisse lieferten (die Resampling-Methode fand auch in anderen Problemen Anwendung). Es lieferte auch einen Beitrag zur Theorie der Zeugenbäume (witness tree), die für den Korrektheitsnachweis benutzt wurden.

Moser und Tardos erhielten dafür 2020 den Gödel-Preis.

Moser konnte außerdem die lokale Suche beim k-SAT-Algorithmus (k ist die Anzahl der Einschränkungen, der randomisierte Algorithmus wurde 1999 von Uwe Schöning vorgestellt) vollständig vom Zufall befreien (de-randomisieren).

Er absolvierte Praktika am CERN und bei Microsoft Research in Redmond. Seit 2013 ist er bei Circular Capital in der Region Basel als Finanzmathematiker (Quant) und Entwickler von Handelssoftware.