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

Email: kbringmampi-inf.mpg.de

I am a professor at Saarland University, and affiliated to 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 working mostly on optimization, strings, and computational geometry.


Awards and Grants


ERC Starting Grant 2019: Technology Transfer between Integer Programming and Efficient Algorithms (TIPEA)

EATCS Presburger Award for Young Scientists 2019

Heinz Maier-Leibnitz-Prize 2019

EATCS Distinguished Dissertation Award 2015

Google European Doctoral Fellowship 2012-2014


Recent Teaching


Winter 2023/24: Sublinear Algorithms

Winter 2023/24: Algorithms and Data Structure

Winter 2022/23: Introduction to Algorithms and Data Structure

Summer 2022: Reading Group: String Algorithms

Summer 2022: Competitive Programming

Winter 2021/22: Fine-Grained Complexity Theory

Winter 2021/22: Algorithms and Data Structures

Winter 2020/21: Algorithms and Data Structures

Summer 2020: Competitive Programming

Summer 2020: Sublinear Algorithms

Summer 2020: Seminar Reading Group Algorithms

Winter 2019/20: Algorithms and Data Structures

Summer 2019: Fine-Grained Complexity Theory

Winter 2018/19: Multivariate Algorithmics


Program Committees


ICALP'24 (Co-Chair), SoCG'24, ICALP'23, WAOA'23, STOC'22, SOSA'22 (Co-Chair), IPEC'21, ESA'20, SOSA'20, CSR'20, FOCS'19, ICALP'19, STACS'19, HALG'18, SoCG’18, ITCS’18, ICALP’17, IPEC’17, ICALP’15, MASSIVE’15, GECCO’12+’13+’14+’15+’16+’17


Selected Publications


For a complete list of publications look here or in DBLP

[31]

"Knapsack with Small Items in Near-Quadratic Time"

Karl Bringmann

STOC'24: Proc. of the 56th ACM Symposium on the Theory of Computing

[30]

"Faster Sublinear-Time Edit Distance"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Tomasz Kociumaka

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

[29]

"Approximating Subset Sum Ratio faster than Subset Sum"

Karl Bringmann

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

[28]

"The Time Complexity of Fully Sparse Matrix Multiplication"

Amir Abboud, Karl Bringmann, Nick Fischer, Marvin Künnemann

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

[27]

"Dynamic Dynamic Time Warping"

Karl Bringmann, Nick Fischer, Ivor van der Hoog, Evangelos Kipouridis, Tomasz Kociumaka, Eva Rotenberg

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

[26]

"Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!"

Karl Bringmann, Alejandro Cassis, Nick Fischer

FOCS'23: Proc. of the 64th Annual IEEE Symposium on Foundations of Computer Science

[25]

"Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics"

Amir Abboud, Karl Bringmann, Nick Fischer

STOC'23: Proc. of the 55th ACM Symposium on the Theory of Computing

Invited to SICOMP special issue

[24]

"Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond"

Amir Abboud, Karl Bringmann, Seri Khoury, Or Zamir

STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing

[23]

"Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime"

Karl Bringmann, Alejandro Cassis, Nick Fischer, Vasileios Nakos

STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing

[22]

"Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution"

Karl Bringmann, Nick Fischer, Vasileios Nakos

SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms

[21]

"Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance"

Karl Bringmann, Anne Driemel, André Nusser, Ioannis Psarros

SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms

[20]

"Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution"

Karl Bringmann, Nick Fischer, Vasileios Nakos

STOC'21: Proc. of the 53rd ACM Symposium on the Theory of Computing

[19]

"A Fine-Grained Perspective on Approximating Subset Sum and Partition"

Karl Bringmann, Vasileios Nakos

SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms

[18]

"On Near-Linear-Time Algorithms for Dense Subset Sum"

Karl Bringmann, Philip Wellnitz

SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms

[17]

"Top-k-Convolution and the Quest for Near-linear Output-sensitive Subset Sum"

Karl Bringmann, Vasileios Nakos

STOC'20: Proc. of the 52nd ACM Symposium on the Theory of Computing

[16]

"Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max"

Karl Bringmann, Marvin Künnemann, Karol Węgrzycki

STOC'19: Proc. of the 51st ACM Symposium on the Theory of Computing

[15]

"Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability"

Karl Bringmann, Marvin Künnemann, André Nusser

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

[14]

"Few Matches or Almost Periodicity: Faster Pattern Matching with Mismatches in Compressed Texts"

Karl Bringmann, Marvin Künnemann, Philip Wellnitz

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

[13]

"SETH-Based Lower Bounds for Subset Sum and Bicriteria Path"

Amir Abboud, Karl Bringmann, Danny Hermelin, Dvir Shabtay

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

Invited to HALG'20 and to TALG special issue

[12]

"A PTAS for l_p-Low Rank Approximation"

Frank Ban, Vijay Bhattiprolu, Karl Bringmann, Pavel Kolev, Euiwoong Lee, David Woodruff

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

[11]

"More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture"

Amir Abboud, Karl Bringmann, Holger Dell, Jesper Nederlof

STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing

[10]

"Fast Fencing"

Mikkel Abrahamsen, Anna Adamaszek, Karl Bringmann, Vincent Cohen-Addad, Mehran Mehr, Eva Rotenberg, Alan Roytman, Mikkel Thorup

STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing

[9]

"Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)"

Karl Bringmann, Paweł Gawrychowski, Shay Mozes, Oren Weimann

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

[8]

"Multivariate Fine-Grained Complexity of Longest Common Subsequence"

Karl Bringmann, Marvin Künnemann

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

[7]

"Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve"

Amir Abboud, Arturs Backurs, Karl Bringmann, Marvin Künnemann

FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science

[6]

"A Dichotomy for Regular Expression Membership Testing"

Karl Bringmann, Allan Grønlund, Kasper Green Larsen

FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science

[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 57th Annual IEEE Symposium on Foundations of Computer Science

Invited to HALG'17 and to SICOMP special issue

[3]

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

Karl Bringmann, Marvin Künnemann

FOCS'15: Proc. of the 56th 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