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 senior researcher 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 working mostly on strings and computational geometry. Previously, I stayed one year at ETH Zurich and four months at the Simons Institute for the Theory of Computing, Berkeley.
Winter 2017/18: Fine-Grained Complexity Theory
Winter 2016/17: Algorithms and Data Structures
Summer 2016: Complexity Theory of Polynomial-Time Problems
For a complete list of publications look here
[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] |
"Fast Fencing" 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] |
"Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve" 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 |
[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 |