L'ancien doctorant Robin Moser re?oit le prestigieux prix G?del
L'un des prix les plus prestigieux dans le domaine de l'informatique théorique a été décerné à Robin Moser (D-INFK) pour sa version algorithmique du lemme local de Lovász.
Le papier "A constructive proof of the general Lovász Local Lemma" a été publié en 2010 dans le Journal of the ACM 57(2) : 11:1-11:15 avec l'auteur Prof. Gábor Tardos.
Ce travail aborde le lemme local de Lovász (LLL), un outil important de la méthode probabiliste, qui permet de prouver l'existence de certains objets, même s'ils ont une probabilité exponentiellement faible de se produire.
La preuve initiale n'était pas algorithmique et les versions algorithmiques suivantes présentaient des pertes de paramètres significatives. Le papier publié fournit un paradigme algorithmique simple et puissant qui transforme presque toutes les applications connues du LLL en algorithmes randomisés qui respectent les limites de la preuve d'existence. Le travail propose en outre un algorithme derandomisé, un algorithme parallèle et une extension du LLL "unilatéral".
Le nouveau paradigme algorithmique implique un rééchantillonnage des variables qui ont généré de mauvais événements. Un tel rééchantillonnage a été utilisé par la suite dans de nombreux autres travaux - même ceux qui ne se réfèrent pas directement au LLL. En outre, le document fournit une preuve élégante de l'exactitude en utilisant des arbres témoins. Les arbres témoins ont eu une influence bien au-delà du LLL et ont inspiré la méthode de "compression entropique" en combinatoire. La force et la simplicité du travail de Moser en font un succès de grande envergure.
? propos de Robin Moser
Robin Moser a obtenu son doctorat en 2012 au Département d'informatique de l'ETH Zurich, où il était membre du groupe de recherche du professeur Emo Welzl. Sa thèse de doctorat portait sur les "Exact Algorithms for Constraint Satisfaction Problems". Sa carrière a comporté des stages à l'Organisation européenne pour la recherche nucléaire (CERN) à Genève et chez Microsoft Research à Redmond, Washington, ?tats-Unis. Depuis 2013, il travaille au développement de logiciels de trading et en tant qu'analyste quantitatif pour Circular Capital dans la région de B?le, en Suisse.
? propos du Prix G?del
Le prix G?del, qui récompense des travaux exceptionnels dans le domaine de l'informatique théorique, est fondé conjointement par l'European Association for Theoretical Computer Science (EATCS) et le Special Interest Group on Algorithms and Computation Theory of the Association for Computing Machinery (ACM SIGACT) et est décerné chaque année. Le 28e Prix G?del sera décerné dans le cadre du 47e Colloque international sur les robots, les langages et la programmation, qui se tiendra du 8 au 11 juillet 2020 à Sarrebruck, en Allemagne. Le prix est nommé en l'honneur de Kurt G?del, en reconnaissance de ses importantes contributions à la logique mathématique.