Decoration
max planck institut
informatik
mpii logo Minerva of the Max Planck Society

Homepage

Bringmann, Karl

Karl Bringmann

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

Email: kbringmampi-inf.mpg.de

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.


Teaching


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

[7]

"On Algebraic Branching Programs of Small Width"

Karl Bringmann, Christian Ikenmeyer, Jeroen Zuiddam

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

[6]

"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

[5]

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

Karl Bringmann

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

[4]

"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

[3]

"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

[2]

"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

[1]

"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