Karl Bringmann

Pour les articles homonymes, voir Bringmann.

Karl Bringmann

Biographie

Domicile	Allemagne
Formation	Université de la Sarre École polytechnique fédérale de Zurich
Activité	Informaticien

Autres informations

A travaillé pour	Université de la Sarre (depuis novembre 2019) Institut Max-Planck d'informatique
Directeur de thèse	Kurt Mehlhorn

modifier - modifier le code - modifier Wikidata

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

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^[1] dont le sujet est « Sampling from Discrete Distributions and Computing Frechet Distances ». 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.

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' hypothèse de temps exponentiel (en) 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.

• En 2019, Karl Bringmann est l'un des dix récipiendaires du Prix Heinz-Maier-Leibnitz^[2].
• 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^[3].
• Toujours en 2019, Karl Bringmann obtient un ERC Starting Grant : Technology Transfer between Integer Programming and Efficient Algorithms (TIPEA)^[4].

• 2014 Karl Bringmann, « Why Walking the Dog Takes Time: Frechet Distance Has No Strongly Subquadratic Algorithms Unless SETH Fails », 55th Annual Symposium on Foundations of Computer Science, IEEE,‎ 2014, p. 661-670.
• 2019 Karl Bringmann, Marvin Künnemann et André Nusser, « Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance », 35th International Symposium on Computational Geometry (SoCG 2019), Leibniz International Proceedings in Informatics (LIPIcs), vol. 129,‎ 2019, p. 661-670 (lire en ligne, consulté le 2 mai 2020).

• Page personnelle
• Publications de Karl Bringmann sur DBLP
• Ressources relatives à la recherche :
  • Digital Bibliography & Library Project
  • Google Scholar
  • Mathematics Genealogy Project

• Portail de l'informatique théorique
• Portail de l’Allemagne