Jakub Tarnawski reçois une Mention Honorable au Prix ACM 2019
© 2020 EPFL
Jakub Tarnawski, diplômé de l’EPFL, a reçu une mention honorable au prix annuel des thèses doctorales de l’Association for Computing Machinery (ACM) pour une thèse qui abordait deux des problèmes les plus centraux dans le domaine de l’optimisation combinatoire.
Tarnawski, qui est maintenant chercheur en informatique pour Microsoft Research, a d'abord obtenu un master en mathématiques et en informatique à l'université de Wrocław. Il s'est ensuite installé à Lausanne pour ses études de doctorat à la Faculté informatique et communications (IC) de l'EPFL, où il a travaillé sur les algorithmes de graphes et d'approximation, des branches classiques de l'informatique théorique qui ont de nombreuses applications importantes dans l'analyse des réseaux en biologie, chimie, recherche opérationnelle, ingénierie et même en sociologie.
ACM est la plus grande société d’informatique éducative et scientifique au monde. Chaque année, elle reconnaît l'excellence de la recherche en décernant un prix annuel et des mentions honorables aux meilleures thèses de doctorat en informatique et en ingénierie. La réussite de Tarnawski marque la première fois qu'un étudiant de l'EPFL reçoit une mention honorable de l'ACM depuis 2005.
S'attaquer aux questions non résolues dans la théorie des graphes
La thèse de Tarnawski intitulée New Graph Algorithms via Polyhedral Techniquesa été décrite par l'ACM comme ayant fait des "progrès algorithmiques révolutionnaires" sur les problèmes d’optimisation de couplage et du voyageur de commerce, catégories de théorie des graphes qui ont intrigué les mathématiciens depuis leur conception dans les années 1800.
Depuis les années 1950, les informaticiens tentent de trouver les meilleures méthodes pour résoudre ces problèmes. Bon nombre des solutions proposées ont été utilisées pour réduire les coûts de production dans le secteur de la fabrication et, plus récemment, dans celui du traitement des images médicales. Les travaux de Tarnawski ont permis d'avancer dans la résolution de plusieurs questions importantes dans ce domaine auxquelles les scientifiques s'attaquent depuis plus d'un demi-siècle.
Une partie de sa thèse a tenté de déterminer si le hasard est nécessaire pour obtenir de rapides algorithmes parallèles de couplage, une question longtemps considérée comme un mystère non résolu en informatique. Ses travaux ont été décrits comme ayant fait des progrès significatifs à cet égard en derandomisant presque complètement un algorithme parallèle randomisé de couplage vieux de trois décennies.
La thèse s'est également appuyée sur les travaux du pionnier de l'informatique de Stanford, George Dantzig, dans les années 1950, et a résolu un cas particulier du problème du voyageur de commerce - la question de trouver le tour le plus court de n villes données - en utilisant un programme linéaire. Tarnawski a pu faire des progrès dans l'analyse de la force de ce programme linéaire, et a développé le premier algorithme d'approximation à facteur constant pour la version asymétrique plus complexe du problème du voyageur de commerce.
"J'ai beaucoup de bons souvenirs de l'époque où Jakub était doctorant", a déclaré Ola Svensson, directeur du programme doctoral de l'EPFL. "Les années 2017-2018 ont été particulièrement magiques avec plusieurs résultats incroyables dont ceux cités dans le communiqué de presse. Je me sens chanceux d'avoir été son directeur de thèse et je suis très heureux qu'il ait reçu cette prestigieuse mention d'honneur".
Tarnawski recevra 5'000 dollars lorsque les prix seront officiellement reconnus lors du banquet annuel de remise des prix de l'ACM, le 3 octobre à San Francisco.