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.


Winter 2016/17: Algorithms and Data Structures

Summer 2016: Complexity Theory of Polynomial-Time Problems

Selected Publications

For a complete list of publications look here


"A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum"

Karl Bringmann

SODA'17: Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms


"Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product"

Karl Bringmann, Fabrizio Grandoni, Barna Saha, Virginia Vassilevska Williams

FOCS'16: Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science


"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


"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