96 citations · 442 across the 64 of their papers we have counts for
6 papers · 1 filter
Impossibility Results for Grammar-Compressed Linear Algebra
Amir Abboud, Arturs Backurs, Karl Bringmann +1
To handle vast amounts of data, it is natural and popular to compress vectors and matrices. When we compress a vector from size down to size , it certainly makes it ea…
On Near-Linear-Time Algorithms for Dense Subset Sum
Karl Bringmann, Philip Wellnitz
In the Subset Sum problem we are given a set of positive integers and a target and are asked whether some subset of sums to . Natural parameters for this problem…
When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation
Karl Bringmann, Marvin Künnemann, André Nusser
Consider the natural question of how to measure the similarity of curves in the plane by a quantity that is invariant under translations of the curves. Such a measure is justified…
Fast and Simple Modular Subset Sum
Kyriakos Axiotis, Arturs Backurs, Karl Bringmann +4
We revisit the Subset Sum problem over the finite cyclic group for some given integer . A series of recent works has provided near-optimal algorithms for this pro…
Scheduling Lower Bounds via AND Subset Sum
Amir Abboud, Karl Bringmann, Danny Hermelin +1
Given instances of Subset Sum, the AND Subset Sum problem asks to determine whether all of these instances are yes-instances; that is, whether each…
Faster Minimization of Tardy Processing Time on a Single Machine
Karl Bringmann, Nick Fischer, Danny Hermelin +2
This paper is concerned with the problem, the problem of minimizing the total processing time of tardy jobs on a single machine. This is not only a fundamental sch…