Karl Bringmann

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

Pour les articles homonymes, voir Bringmann.

Karl Bringmann
Biographie
Domicile
Formation
Activité
Autres informations
A travaillé pour
Dir. de thèse

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[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.

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' 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.

Prix et distinctions

Publications (sélection)

  • 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, , 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, , p. 661-670 (lire en ligne, consulté le ).

Notes et références

Liens externes

  • Portail de l'informatique théorique
  • Portail de l’Allemagne
Cet article est issu de Wikipedia. Le texte est sous licence Creative Commons - Attribution - Partage dans les Mêmes. Des conditions supplémentaires peuvent s'appliquer aux fichiers multimédias.