max planck institut
mpii logo Minerva of the Max Planck Society


Bringmann, Karl

Karl Bringmann

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Campus E1 4, Room 305
66123, Saarbrücken


I am a researcher at Max Planck Institute for Informatics. I am interested in theoretical computer science in general. More specifically, I study conditional lower bounds (e.g. based on the Strong Exponential Time Hypothesis), algorithm design including but not limited to computational geometry, and random graph models for real world networks. I recently rejoined MPI after staying one year at ETH Zurich and four months at the Simons Institute for the Theory of Computing, Berkeley.

The best way to reach me is by e-mail.

Selected Publications

For a complete list of publications look here


"Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping"

Karl Bringmann, Marvin Künnemann

FOCS'15: Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science


"Approximability of the Discrete Fréchet Distance"

Karl Bringmann, Wolfgang Mulzer

SoCG'15: Proc. of the 31st International Symposium on Computational Geometry


"Why walking the dog takes time: Frechet distance has no strongly subquadratic algorithms unless SETH fails"

Karl Bringmann

FOCS'14: Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science


"Balls into bins via local search: cover time and maximum load"

Karl Bringmann, Thomas Sauerwald, Alexandre Stauffer, He Sun

STACS'14: Proc. of the 31st Symposium on Theoretical Aspects of Computer Science


"Succinct Sampling from Discrete Distributions"

Karl Bringmann, Kasper Green Larsen

STOC'13: Proc. of the 45th ACM Symposium on the Theory of Computing


"Efficient Sampling Methods for Discrete Distributions"

Karl Bringmann, Konstantinos Panagiotou

ICALP'12: Proc. of the 39th International Colloquium on Automata, Languages and Programming


"Klee's measure problem on fat boxes in time O(n(d+2)/3)"

Karl Bringmann

SoCG'10: Proc. of the 2010 Annual Symposium on Computational Geometry

Short CV