96 citations · 442 across the 64 of their papers we have counts for
8 papers · 1 filter
Faster Sublinear-Time Edit Distance
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation al…
Dynamic Dynamic Time Warping
Karl Bringmann, Nick Fischer, Ivor van der Hoog +3
The Dynamic Time Warping (DTW) distance is a popular similarity measure for polygonal curves (i.e., sequences of points). It finds many theoretical and practical applications, espe…
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
Karl Bringmann, Allan Grønlund, Marvin Künnemann +1
We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphab…
Approximating Subset Sum Ratio faster than Subset Sum
Karl Bringmann
Subset Sum Ratio is the following optimization problem: Given a set of positive numbers , find disjoint subsets minimizing the ratio $\max\{Σ(X)/Σ(Y),Σ(Y)/…
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…
Knapsack with Small Items in Near-Quadratic Time
Karl Bringmann
The Knapsack problem is one of the most fundamental NP-complete problems at the intersection of computer science, optimization, and operations research. A recent line of research w…