Robin A. Moser

Robin Alexander Moser (né le 14 août 1983 ; résident à Inkwil) est un informaticien suisse travaillant sur les algorithmes combinatoires et le problème SAT.

Moser obtient son doctorat à l'École polytechnique fédérale de Zurich en 2012 sous la direction d'Emo Welzl. Pour sa thèse (Exact Algorithms for Constraint Satisfaction Problems), il reçoit le prix de la meilleure thèse dans la région germanophone de la Gesellschaft für Informatik. Sa thèse porte sur le Lemme local de Lovász (LLL), qui fournit des critères forts pour la satisfaisabilité des problèmes avec contraintes comme dans les formules de la logique propositionnelle. Dans le cadre des méthodes probabilistes, il est utilisé pour montrer l'existence d'objets, même s'ils sont très improbables. Moser développe une preuve constructive (algorithmique) étonnamment simple du lemme (la preuve originale était non constructive, étendue peu après avec Gábor Tardos. Leurs travaux ont permis de transformer presque toutes les applications connues de LLL en algorithmes randomisés avec rééchantillonnage de variables, méthode qui avait donné de mauvais résultats (la méthode de rééchantillonnage a également été utilisée dans d'autres problèmes). Moser contribue également à la théorie des arbres témoins (witness tree) utilisés pour les preuves de correction.

Moser et Tardos reçoivent le prix Gödel en 2020 pour leur article.

Moser a également pu dérandomiser la recherche locale dans l'algorithme k-SAT (où k est le nombre de contraintes), où un algorithme randomisé a été développé par Uwe Schöning en 1999.

Moser effectue des stages au CERN et chez Microsoft Research à Redmond. Depuis 2013, il travaille chez Circular Capital dans la région de Bâle en tant que mathématicien financier (analyste quantitatifou Quant) et développeur de logiciels de trading.

En plus des travaux cités dans les notes :

• Heidi Gebauer, Robin A. Moser, Dominik Scheder et Emo Welzl, « The Lovász local lemma and satisfiability », dans Efficient algorithms. Essays dedicated to Kurt Mehlhorn on the occasion of his 60th birthday, coll. « Lecture Notes in Computer Science » (n 5760), 2009, p. 30-54.
• Robin A. Moser et Dominik Scheder, « A full derandomization of Schöning's k-SAT algorithm », 43e STOC,‎ 2011, p. 245–252 .
• Kevin Buchin, Jiří Matoušek, Robin A. Moser et Dömötör Pálvölgyi, « Vectors in a box », Mathematical Programming, Séries A et B, vol. 135, n 1–2,‎ octobre 2012, p. 323–335 .
• avec 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
• avec Heidi Gebauer, Anna Gundert, Yoshio Okamoto : « Not All Saturated 3-Forests Are Tight », Arxiv 2011