Finaliste Prix EPFL de doctorats 2019 - Damian Straszak
Mention spéciale du jury à Damian Straszak pour sa thèse “New Algorithmic Paradigms for Discrete Problems using Dynamical Systems and Polynomials”
Thèse EPFL n°8957 (2018)
Directeur de thèse : Prof. N. Vishnoi
L'optimisation est un outil fondamental en science. Les innovations récentes dans l'application de l'optimisation à des problèmes importants en biologie, en économie, en physique et en statistique posent de nouveaux défis à la conception des algorithmes. Ces problèmes d'optimisation doivent être résolus. Le premier défi est lié à la taille sans cesse croissante des instances, ce qui oblige les algorithmes sous-jacents à s'exécuter dans un temps linéaire à la taille des données d'entrée. Le deuxième défi est lié à l'émergence de nouveaux problèmes difficiles qui doivent être résolus même s'ils sont considérés comme insolubles sur le plan mathématique en raison de leur caractère NP-complet ou non convexe.
La première partie de cette thèse tente de relever le premier défi : l'efficacité. Nous étudions de nouveaux algorithmes pour les problèmes combinatoires classiques basés sur des systèmes dynamiques continus inspirés par l'étude d'une moisissure visqueuse, Physarum polycephalum. Nous effectuons une analyse mathématique rigoureuse de ces systèmes dynamiques et en extrayons de nouveaux algorithmes rapides.
Dans la deuxième partie, nous développons de nouveaux outils pour relever le défi de l'insolubilité. Nous étudions des problèmes d'optimisation discrète difficiles ainsi que leurs équivalentes en échantillonnage et en comptage, y compris le calcul des couplages dans les graphes, le calcul du permanent des matrices ou l'échantillonnage via des processus ponctuels déterminantaux. Nous présentons un cadre général, basé sur des polynômes, pour traiter ces problèmes par calcul.