Robin A. Moser – Wikipedia

Robin Alexander Moser (* 14. August 1983; heimatberechtigt in Inkwil)^[1] 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.^[2] 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).^[3], bald darauf mit Gábor Tardos ausgebaut.^[4] 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.^[5]

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.

Außer die in den Fußnoten zitierten Arbeiten.

• mit Heidi Gebauer, Dominik Scheder, Emo Welzl: The Lovász Local Lemma and Satisfiability, in: Susanne Albers, Helmut Alt, Stefan Näher (Hrsg.), Efficient Algorithms, Lecture Notes in Computer Science 5760, Springer 2009, S. 30–54
• mit Timon Hertli, Dominik Scheder: Improving PPSZ for 3-SAT using Critical Variables, Arxiv 2010
• mit Dominik Scheder: A full derandomization of Schöning’s k-SAT algorithm, Proceedings of the 43th Annual ACM Symposium on Theory of computing (STOC), 2011, S. 245–252, Arxiv
• mit Kevin Buchin, Jiří Matoušek, Dömötör Pálvölgyi: Vectors in a box, Mathematical Programming, Series A and B, Band 135, Oktober 2012, Heft 1–2
• mit T. Hertli, I. Hurbain, S. Millius: The PPSZ Algorithm for Constraint Satisfaction Problems on More Than Two Colors, Conference on Principles and Practice of Constraint Programming 2016
• mit Heidi Gebauer, Anna Gundert, Yoshio Okamoto: Not All Saturated 3-Forests Are Tight, Arxiv 2011

1. ↑ Robin Alexander Moser: Exact Algorithms for Constraint Satisfaction Problems. 2012, doi:10.3929/ethz-a-009755667.
2. ↑ GI-Dissertationspreis für Robin Moser von der ETH Zürich, Gesellschaft für Informatik, 4. Oktober 2013
3. ↑ Robin A. Moser: A constructive proof of the Lovasz Local Lemma, Arxiv 2008. Auch veröffentlicht in Proceedings of the 41th Annual ACM Symposium on Theory of computing (STOC), 2009
4. ↑ R. A. Moser, G. Tardos, A constructive proof of the general Lovasz Local Lemma, Arxiv 2009, Journal of the ACM, Band 47, 2010, Heft 2, S. 1–11
5. ↑ Amanda Caracas-Egger: Ehemaliger Doktorand Robin Moser erhält renommierten Gödel-Preis, ETH Zürich, 6. April 2020