Karl Bringmann (né le ) est un informaticien théoricien allemand. Il est chercheur à l'Institut Max-Planck d'informatique à Sarrebruck.

Biographie Bringmann étudie l'informatique à l'Université de la Sarre de 2006 à 2014. Il soutient fin 2014 une thèse de doctorat à l'Université de la Sarre sous la supervision de Kurt Mehlhorn dont le sujet est . Il est ensuite postdoc à l'ETH Zurich, puis Research Fellow au Simons Institute for the Theory of Computing de Berkeley jusqu'à fin 2015. Il est ensuite à l'Institut Max-Planck d'informatique, d'abord en postdoc, puis comme senior researcher.

Recherche

Bringmann s'intéresse à l'informatique théorique, et plus spécifiquement, il étudie les bornes inférieures sous certaines conditions (par exemple, sur la base de l' forte (dont l'acronyme est « SETH ») et la conception d'algorithmes en algorithmique du texte et en géométrie algorithmique.

Les auteurs du laudatio du prix Presburger mettent en avant son article « Why walking the dog takes time: Fréchet distance has no strongly subquadratic algorithms unless SETH fails » (Symposium on Foundations of Computer Science, 2014). Les bornes inférieures strictes obtenues par Bringmann sous l'hypothèse de temps exponentiel fort (SETH) pour plusieurs problèmes algorithmiques classiques expliquent la longue absence de progrès algorithmique en dehors de la technique classique de la programmation dynamique. L'article de Bringmann sur la distance de Fréchet a déclenché un axe de recherche très fructueux pour d'autres problèmes classiques, y compris les problèmes de similarité de séquences tels que la distance d'édition, la plus longue sous-séquence commune, la distance d'édition sur les arbres et les problèmes de chaînes compressées.

Prix et distinctions En 2019, Karl Bringmann est l'un des dix récipiendaires du Prix Heinz-Maier-LeibnitzRécipiendaires du Prix Heinz-Maier-Leibnitz 2019.. En 2019 également, Bringmann est lauréat, avec Kasper Green Larsen du prix Presburger décerné par l'European Association for Theoretical Computer Science pour ses travaux sur les bornes inférieurs.. Toujours en 2019, Karl Bringmann obtient un ERC Starting Grant : Technology Transfer between Integer Programming and Efficient Algorithms (TIPEA)Récipiendaires des starting grants 2019..

Publications (sélection) 2014 . 2019 .

Notes et références

Liens externes Page personnelle Publications de Karl Bringmann sur DBLP

Catégorie:Personnalité allemande de l'informatique