Robin Alexander Moser (né le ; résident à Inkwil). est un informaticien suisse travaillant sur les algorithmes combinatoires et le problème SAT.
Biographie 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 Société pour l'informatique« GI-Dissertationspreis für Robin Moser von der ETH Zürich », Gesellschaft für Informatik, 4 octobre 2013.. 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 articleAmanda Caracas-Egger, « Ehemaliger Doktorand Robin Moser erhält renommierten Gödel-Preis », ETH Zürich, 6 avril 2020..
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 quantitatif ou Quant) et développeur de logiciels de trading.
Publications (sélection)
En plus des travaux cités dans les notes :
. . . 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
Notes et références
Liens externes
Catégorie:Mathématicien suisse du XXIe siècle Catégorie:Naissance en août 1983 Catégorie:Informaticien afro-américain