28 citations · 52 across the 28 of their papers we have counts for
6 papers · 2 filters
Approximation Algorithms for -Low Rank Approximation
Karl Bringmann, Pavel Kolev, David P. Woodruff
We study the -Low Rank Approximation Problem, where the goal is, given an matrix , to output a rank- matrix for which is minimized. Her…
Truly Sub-cubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
Karl Bringmann, Fabrizio Grandoni, Barna Saha +1
It is a major open problem whether the -product of two matrices has a truly sub-cubic (i.e. for ) time algorithm, in particular since it is…
A Note on Hardness of Diameter Approximation
Karl Bringmann, Sebastian Krinninger
We revisit the hardness of approximating the diameter of a network. In the CONGEST model of distributed computing, rounds are necessary to compute the diameter [Fri…
Improved Algorithms for Computing the Cycle of Minimum Cost-to-Time Ratio in Directed Graphs
Karl Bringmann, Thomas Dueholm Hansen, Sebastian Krinninger
We study the problem of finding the cycle of minimum cost-to-time ratio in a directed graph with nodes and edges. This problem has a long history in combinatorial optim…
SETH-Based Lower Bounds for Subset Sum and Bicriteria Path
Amir Abboud, Karl Bringmann, Danny Hermelin +1
Subset-Sum and k-SAT are two of the most extensively studied problems in computer science, and conjectures about their hardness are among the cornerstones of fine-grained complexit…
Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (unless APSP can)
Karl Bringmann, Paweł Gawrychowski, Shay Mozes +1
The edit distance between two rooted ordered trees with nodes labeled from an alphabet~ is the minimum cost of transforming one tree into the other by a sequence of elementa…