Homepage

Karl Bringmann

Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity

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.

Job Openings

I am looking for new PhD students and postdocs.

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 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

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

[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
[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, André 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

Since November 2019:
Professor at Saarland University
January 2016 - October 2019:
PostDoc and Senior Researcher (since 2017) at Max Planck Institute for Informatics
August 2015 - December 2015:
Research Fellow at the Simons Institute for the Theory of Computing, Berkeley, participating in the program "Fine-Grained Complexity and Algorithm Design"
September 2014 - August 2015:
PostDoc at ETH Zurich, holding an ETH Zurich Postdoctoral Fellowship
April 2011 - August 2014:
Ph. D. student in Computer Science at Saarland University, Saarbrücken, Germany and Max Planck Institute for Informatics, under supervision of Kurt Mehlhorn
Holding a Google European Doctoral Fellowship since 2012
Thesis won an EATCS Distinguished Dissertation Award