8 citations · 14 across the 11 of their papers we have counts for
5 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 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…
Can You Solve Closest String Faster than Exhaustive Search?
Amir Abboud, Nick Fischer, Elazar Goldenberg +2
We study the fundamental problem of finding the best string to represent a given set, in the form of the Closest String problem: Given a set of strings, find…
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Karl Bringmann, Alejandro Cassis, Nick Fischer
In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wu…