28 citations · 52 across the 28 of their papers we have counts for
4 papers · 2 filters
Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS
Karl Bringmann, Bhaskar Ray Chaudhury
We study sketching and streaming algorithms for the Longest Common Subsequence problem (LCS) on strings of small alphabet size . For the problem of deciding whether the LCS of…
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
Karl Bringmann, Marvin Künnemann, André Nusser
The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection…
A PTAS for -Low Rank Approximation
Frank Ban, Vijay Bhattiprolu, Karl Bringmann +3
A number of recent works have studied algorithms for entrywise -low rank approximation, namely, algorithms which given an matrix (with ), output…
Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth
Karl Bringmann, Thore Husfeldt, Måns Magnusson
We show that the eccentricities, diameter, radius, and Wiener index of an undirected -vertex graph with nonnegative edge lengths can be computed in time $O(n\cdot \binom{k+\lcei…