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 coordinater 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) and algorithm design including but not limited to computational geometry. Previously, I stayed 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