96 citations · 442 across the 64 of their papers we have counts for
11 papers · 1 filter
Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry
Karl Bringmann
Fine-grained complexity theory is the area of theoretical computer science that proves conditional lower bounds based on the Strong Exponential Time Hypothesis and similar conjectu…
Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution
Karl Bringmann, Nick Fischer, Vasileios Nakos
Computing the convolution of two length- integer vectors is a core problem in several disciplines. It frequently comes up in algorithms for Knapsack, -SUM, A…
Fine-Grained Completeness for Optimization in P
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We initiate the study of fine-grained completeness theorems for exact and approximate optimization in the polynomial-time regime. Inspired by the first completeness results for dec…
Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum
Karl Bringmann, Vasileios Nakos
In the classical Subset Sum problem we are given a set and a target , and the task is to decide whether there exists a subset of which sums to . A recent line of rese…
Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance
Karl Bringmann, Anne Driemel, André Nusser +1
We study the -approximate near neighbor problem under the continuous Fréchet distance: Given a set of polygonal curves with vertices, a radius , and a parameter $k…
Traversing the FFT Computation Tree for Dimension-Independent Sparse Fourier Transforms
Karl Bringmann, Michael Kapralov, Mikhail Makarov +3
We consider the well-studied Sparse Fourier transform problem, where one aims to quickly recover an approximately Fourier -sparse vector from…