96 citations · 442 across the 64 of their papers we have counts for
13 papers · 1 filter
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…
Polyline Simplification has Cubic Complexity
Karl Bringmann, Bhaskar Ray Chaudhury
In the classic polyline simplification problem we want to replace a given polygonal curve , consisting of vertices, by a subsequence of vertices from such that…
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…
More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture
Amir Abboud, Karl Bringmann, Holger Dell +1
The Strong Exponential Time Hypothesis and the OV-conjecture are two popular hardness assumptions used to prove a plethora of lower bounds, especially in the realm of polynomial-ti…
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…