max planck institut
informatik
informatik
Max-Planck-Institut für Informatik
Department 1: Algorithms and Complexity
Email:
kbringma
mpi-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.
EATCS Presburger Award for Young Scientists 2019
Heinz Maier-Leibnitz-Prize 2019
EATCS Distinguished Dissertation Award 2015
Google European Doctoral Fellowship 2012-2014
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
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
For a complete list of publications look here or in DBLP
| [30] |
"Faster Sublinear-Time Edit Distance" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [29] |
"Approximating Subset Sum Ratio faster than Subset Sum" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [28] |
"The Time Complexity of Fully Sparse Matrix Multiplication" SODA'24: Proc. of the 35th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [27] |
"Dynamic Dynamic Time Warping" 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!" 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" STOC'23: Proc. of the 55th ACM Symposium on the Theory of Computing Invited to SICOMP special issue |
| [24] |
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" STOC'22: Proc. of the 54th ACM Symposium on the Theory of Computing |
| [22] |
"Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution" 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" SODA'22: Proc. of the 33rd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [20] |
"Sparse Nonnegative Convolution is Equivalent to Dense Nonnegative Convolution" STOC'21: Proc. of the 53rd ACM Symposium on the Theory of Computing |
| [19] |
"A Fine-Grained Perspective on Approximating Subset Sum and Partition" SODA'21: Proc. of the 32nd Annual ACM-SIAM Symposium on Discrete Algorithms |
| [18] |
"On Near-Linear-Time Algorithms for Dense Subset Sum" 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" 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" STOC'19: Proc. of the 51st ACM Symposium on the Theory of Computing |
| [15] |
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" SODA'19: Proc. of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [13] |
"SETH-Based Lower Bounds for Subset Sum and Bicriteria Path" 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" SODA'19: Proc. of the 30th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [11] |
"More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture" STOC'18: Proc. of the 50th ACM Symposium on the Theory of Computing |
| [10] |
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)" SODA'18: Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [8] |
"Multivariate Fine-Grained Complexity of Longest Common Subsequence" SODA'18: Proc. of the 29th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [7] |
FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science |
| [6] |
"A Dichotomy for Regular Expression Membership Testing" FOCS'17: Proc. of the 58th Annual IEEE Symposium on Foundations of Computer Science |
| [5] |
"A Near-Linear Pseudopolynomial Time Algorithm for Subset Sum" SODA'17: Proc. of the 28th Annual ACM-SIAM Symposium on Discrete Algorithms |
| [4] |
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" FOCS'15: Proc. of the 56th Annual IEEE Symposium on Foundations of Computer Science |
| [2] |
FOCS'14: Proc. of the 55th Annual IEEE Symposium on Foundations of Computer Science |
| [1] | "Succinct Sampling from Discrete Distributions" STOC'13: Proc. of the 45th ACM Symposium on the Theory of Computing |