Robin A. Moser
| Naissance | |
|---|---|
| Nationalité | |
| Formation |
École polytechnique fédérale de Zurich (doctorat) (jusqu'en ) |
| Activités |
| Dir. de thèse |
Emo Welzl |
|---|---|
| Distinction |
Prix Gödel () |
Robin Alexander Moser (né le ; résident à Inkwil)[1] est un informaticien suisse travaillant sur les algorithmes combinatoires et le problème SAT.
Biographie[modifier | modifier le code]
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[2]. 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[3], étendue peu après avec Gábor Tardos[4]. 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[5].
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)[modifier | modifier le code]
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 » (no 5760), , p. 30-54.
- Robin A. Moser et Dominik Scheder, « A full derandomization of Schöning's k-SAT algorithm », 43e STOC, , p. 245–252 (arXiv 1008.4067).
- 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, nos 1–2, , p. 323–335 (DOI 10.1007/s10107-011-0474-y, arXiv 0912.0424).
- 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[modifier | modifier le code]
- Robin Alexander Moser, « Exact Algorithms for Constraint Satisfaction Problems », ETH Zürich Research Collection, (DOI 10.3929/ethz-a-009755667).
- « GI-Dissertationspreis für Robin Moser von der ETH Zürich », Gesellschaft für Informatik, 4 octobre 2013.
- Robin A. Moser, « A constructive proof of the Lovász local lemma », Proceedings of the 41st annual ACM symposium on theory of computing, STOC ’09., , p. 343-350 (arXiv 0810.4812).
- Robin A. Moser et Gábor Tardos, « A constructive proof of the general Lovász local lemma », Journal of the ACM, vol. 57, no 2, , article no 11 (15 pages) (zbMATH 1300.60024, arXiv 0903.0544).
- Amanda Caracas-Egger, « Ehemaliger Doktorand Robin Moser erhält renommierten Gödel-Preis », ETH Zürich, 6 avril 2020.
Liens externes[modifier | modifier le code]
- Ressources relatives à la recherche :
