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.
I am looking for new PhD students and postdocs.
EATCS Presburger Award for Young Scientists 2019
Heinz Maier-Leibnitz-Prize 2019
EATCS Distinguished Dissertation Award 2015
Google European Doctoral Fellowship 2012-2014
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
[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 |
[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 |