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.


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


"On Algebraic Branching Programs of Small Width"

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

CCC'17: Proc. of the 32th Conference on Computational Complexity


"Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs"

Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger

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


"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


"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

Short CV