96 citations · 442 across the 64 of their papers we have counts for
11 papers · 1 filter
Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics
Amir Abboud, Karl Bringmann, Nick Fischer
The "short cycle removal" technique was recently introduced by Abboud, Bringmann, Khoury and Zamir (STOC '22) to prove fine-grained hardness of approximation. Its main technical re…
Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries
Karl Bringmann, Nofar Carmeli
We study the enumeration of answers to Unions of Conjunctive Queries (UCQs) with optimal time guarantees. More precisely, we wish to identify the queries that can be solved with li…
Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution
Karl Bringmann, Alejandro Cassis
We present new exact and approximation algorithms for 0-1-Knapsack and Unbounded Knapsack: * Exact Algorithm for 0-1-Knapsack: 0-1-Knapsack has known algorithms running in time $\w…
Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds
Bahareh Banyassady, Mark de Berg, Karl Bringmann +6
We consider the unlabeled motion-planning problem of unit-disc robots moving in a simple polygonal workspace of edges. The goal is to find a motion plan that moves the robo…
Improved Sublinear-Time Edit Distance for Preprocessed Strings
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the problem of approximating the edit distance of two strings in sublinear time, in a setting where one or both string(s) are preprocessed, as initiated by Goldenberg, Rub…
A Structural Investigation of the Approximability of Polynomial-Time Problems
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the systematic study of a recently introduced polynomial-time analogue of MaxSNP, which includes a large number of well-studied problems (including Nearest and Furthest…