| Hjem | Tyskland |
|---|---|
| Opplæring | Universitetet i Saarland |
| Aktivitet | Informatiker |
Karl Bringmann (født den15. juni 1986) er en tysk teoretisk informatiker . Han er forsker ved Max-Planck Institute for Informatics i Saarbrücken.
Bringmann studerte informatikk ved University of the Saar fra 2006 til 2014. På slutten av 2014 forsvarte han en doktorgradsavhandling ved University of the Saar under veiledning av Kurt Mehlhorn, hvis fag er " Sampling from Discrete Distributions and Computing Frechet Distances" ” . Han var deretter postdoktor ved ETH Zurich , deretter stipendiat ved Simons Institute for Theory of Computing i Berkeley til slutten av 2015. Han var da ved Max-Planck Institute for Computer Science , først i postdoc, deretter som seniorforsker .
Bringmann er interessert i teoretisk informatikk, spesielt undersøker den de nedre grensene under visse forhold (f.eks. Basert på den eksponentielle tidshypotesen (in) høy (hvis akronym er "Seth") og utformingen av algoritmer i tekstalgoritmer og beregningsgeometri .
Forfatterne av Presburger-prisen laudatio fremhever sin artikkel “Why walking the dog takes time: Fréchet distance has no stark subquadratic algoritms without SETH mislykkes” (Symposium on Foundations of Computer Science, 2014). De strenge nedre grensene som Bringmann oppnår under antagelsen om sterk eksponentiell tid (SETH) for flere klassiske algoritmiske problemer, forklarer det lange fraværet av algoritmisk fremgang utenfor den klassiske teknikken for dynamisk programmering . Bringmanns artikkel om Fréchet-avstand utløste en veldig fruktbar forskningslinje for andre klassiske problemer, inkludert sekvenslikhetsproblemer som redigeringsavstand , lengste vanlige undersøkelse , redigeringsavstand på trær og problemer med komprimerte strenger.