Karl Bringmann

research

∙ 09/12/2023

The Time Complexity of Fully Sparse Matrix Multiplication

What is the time complexity of matrix multiplication of sparse integer m...

0 Amir Abboud, et al. ∙

research

∙ 08/06/2023

Knapsack with Small Items in Near-Quadratic Time

The Bounded Knapsack problem is one of the most fundamental NP-complete ...

0 Karl Bringmann, et al. ∙

research

∙ 05/02/2023

Faster 0-1-Knapsack via Near-Convex Min-Plus-Convolution

We revisit the classic 0-1-Knapsack problem, in which we are given n ite...

0 Karl Bringmann, et al. ∙

research

∙ 04/11/2023

Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!

In this work we revisit the fundamental Single-Source Shortest Paths (SS...

0 Karl Bringmann, et al. ∙

research

∙ 11/14/2022

Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics

The "short cycle removal" technique was recently introduced by Abboud, B...

0 Amir Abboud, et al. ∙

research

∙ 10/21/2022

Unbalanced Triangle Detection and Enumeration Hardness for Unions of Conjunctive Queries

We study the enumeration of answers to Unions of Conjunctive Queries (UC...

0 Karl Bringmann, et al. ∙

research

∙ 05/17/2022

Faster Knapsack Algorithms via Bounded Monotone Min-Plus-Convolution

We present new exact and approximation algorithms for 0-1-Knapsack and U...

0 Karl Bringmann, et al. ∙

research

∙ 05/16/2022

Unlabeled Multi-Robot Motion Planning with Tighter Separation Bounds

We consider the unlabeled motion-planning problem of m unit-disc robots ...

0 Bahareh Banyassady, et al. ∙

research

∙ 04/29/2022

Improved Sublinear-Time Edit Distance for Preprocessed Strings

We study the problem of approximating the edit distance of two strings i...

0 Karl Bringmann, et al. ∙

research

∙ 04/25/2022

A Structural Investigation of the Approximability of Polynomial-Time Problems

We initiate the systematic study of a recently introduced polynomial-tim...

0 Karl Bringmann, et al. ∙

research

∙ 04/22/2022

Hardness of Approximation in P via Short Cycle Removal: Cycle Detection, Distance Oracles, and Beyond

We present a new technique for efficiently removing almost all short cyc...

0 Amir Abboud, et al. ∙

research

∙ 03/15/2022

Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves

The Dynamic Time Warping (DTW) distance is a popular measure of similari...

0 Karl Bringmann, et al. ∙

research

∙ 03/07/2022

Towards Sub-Quadratic Diameter Computation in Geometric Intersection Graphs

We initiate the study of diameter computation in geometric intersection ...

0 Karl Bringmann, et al. ∙

research

∙ 02/16/2022

Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime

We revisit the task of computing the edit distance in sublinear time. In...

0 Karl Bringmann, et al. ∙

research

∙ 01/07/2022

Tight Fine-Grained Bounds for Direct Access on Join Queries

We consider the task of lexicographic direct access to query answers. Th...

0 Karl Bringmann, et al. ∙

research

∙ 10/19/2021

Fine-Grained Complexity Theory: Conditional Lower Bounds for Computational Geometry

Fine-grained complexity theory is the area of theoretical computer scien...

0 Karl Bringmann, et al. ∙

research

∙ 07/28/2021

Top-k-Convolution and the Quest for Near-Linear Output-Sensitive Subset Sum

In the classical Subset Sum problem we are given a set X and a target t,...

0 Karl Bringmann, et al. ∙

research

∙ 07/16/2021

Tight Bounds for Approximate Near Neighbor Searching for Time Series under the Fréchet Distance

We study the c-approximate near neighbor problem under the continuous Fr...

0 Karl Bringmann, et al. ∙

research

∙ 07/15/2021

Deterministic and Las Vegas Algorithms for Sparse Nonnegative Convolution

Computing the convolution A⋆ B of two length-n integer vectors A,B is a ...

0 Karl Bringmann, et al. ∙

research

∙ 07/15/2021

Sparse Fourier Transform by traversing Cooley-Tukey FFT computation graphs

Computing the dominant Fourier coefficients of a vector is a common task...

0 Karl Bringmann, et al. ∙

research

∙ 07/04/2021

Fine-Grained Completeness for Optimization in P

We initiate the study of fine-grained completeness theorems for exact an...

0 Karl Bringmann, et al. ∙

research

∙ 06/15/2021

A Linear-Time n^0.4-Approximation for Longest Common Subsequence

We consider the classic problem of computing the Longest Common Subseque...

0 Karl Bringmann, et al. ∙

research

∙ 05/12/2021

Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution

Computing the convolution A⋆ B of two length-n vectors A,B is an ubiquit...

0 Karl Bringmann, et al. ∙

research

∙ 05/11/2021

Current Algorithms for Detecting Subgraphs of Bounded Treewidth are Probably Optimal

The Subgraph Isomorphism problem is of considerable importance in comput...

0 Karl Bringmann, et al. ∙

research

∙ 05/09/2021

Fast n-fold Boolean Convolution via Additive Combinatorics

We consider the problem of computing the Boolean convolution (with wrapa...

0 Karl Bringmann, et al. ∙

research

∙ 01/19/2021

Translating Hausdorff is Hard: Fine-Grained Lower Bounds for Hausdorff Distance Under Translation

Computing the similarity of two point sets is a ubiquitous task in medic...

0 Karl Bringmann, et al. ∙

research

∙ 10/27/2020

Impossibility Results for Grammar-Compressed Linear Algebra

To handle vast amounts of data, it is natural and popular to compress ve...

0 Amir Abboud, et al. ∙

research

∙ 10/18/2020

On Near-Linear-Time Algorithms for Dense Subset Sum

In the Subset Sum problem we are given a set of n positive integers X an...

0 Karl Bringmann, et al. ∙

research

∙ 08/24/2020

Fast and Simple Modular Subset Sum

We revisit the Subset Sum problem over the finite cyclic group ℤ_m for s...

0 Kyriakos Axiotis, et al. ∙

research

∙ 08/17/2020

When Lipschitz Walks Your Dog: Algorithm Engineering of the Discrete Fréchet Distance under Translation

Consider the natural question of how to measure the similarity of curves...

0 Karl Bringmann, et al. ∙

research

∙ 03/16/2020

Scheduling Lower Bounds via AND Subset Sum

Given N instances (X_1,t_1),...,(X_N,t_N) of Subset Sum, the AND Subset ...

0 Amir Abboud, et al. ∙

research

∙ 03/16/2020

Faster Minimization of Tardy Processing Time on a Single Machine

This paper is concerned with the 1||∑ p_jU_j problem, the problem of min...

0 Karl Bringmann, et al. ∙

research

∙ 12/28/2019

Approximating Subset Sum is equivalent to Min-Plus-Convolution

Approximating Subset Sum is a classic and fundamental problem in compute...

0 Karl Bringmann, et al. ∙

research

∙ 07/25/2019

Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max

Zwick's (1+ε)-approximation algorithm for the All Pairs Shortest Path (A...

0 Karl Bringmann, et al. ∙

research

∙ 01/06/2019

Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance

The Fréchet distance provides a natural and intuitive measure for the po...

0 Karl Bringmann, et al. ∙

research

∙ 10/25/2018

Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability

The discrete Fréchet distance is a popular measure for comparing polygon...

0 Karl Bringmann, et al. ∙

research

∙ 10/02/2018

Sketching, Streaming, and Fine-Grained Complexity of (Weighted) LCS

We study sketching and streaming algorithms for the Longest Common Subse...

0 Karl Bringmann, et al. ∙

research

∙ 10/01/2018

Polyline Simplification has Cubic Complexity

In the classic polyline simplification problem we want to replace a give...

0 Karl Bringmann, et al. ∙

research

∙ 07/16/2018

A PTAS for ℓ_p-Low Rank Approximation

A number of recent works have studied algorithms for entrywise ℓ_p-low r...

0 Frank Ban, et al. ∙

research

∙ 05/22/2018

More Consequences of Falsifying SETH and the Orthogonal Vectors Conjecture

The Strong Exponential Time Hypothesis and the OV-conjecture are two pop...

0 Amir Abboud, et al. ∙

research

∙ 05/18/2018

Multivariate Analysis of Orthogonal Range Searching and Graph Distances Parameterized by Treewidth

We show that the eccentricities, diameter, radius, and Wiener index of a...

0 Karl Bringmann, et al. ∙

research

∙ 04/24/2018

Tighter Connections Between Formula-SAT and Shaving Logs

A noticeable fraction of Algorithms papers in the last few decades impro...

0 Amir Abboud, et al. ∙

research

∙ 03/31/2018

Fast Fencing

We consider very natural "fence enclosure" problems studied by Capoyleas...

0 Mikkel Abrahamsen, et al. ∙

research

∙ 03/02/2018

Multivariate Fine-Grained Complexity of Longest Common Subsequence

We revisit the classic combinatorial pattern matching problem of finding...

0 Karl Bringmann, et al. ∙

research

∙ 03/02/2018

Maximum Volume Subset Selection for Anchored Boxes

Let B be a set of n axis-parallel boxes in R^d such that each box has a ...

0 Karl Bringmann, et al. ∙

research

∙ 03/02/2018

A fast implementation of near neighbors queries for Fréchet distance (GIS Cup)

This paper describes an implementation of fast near-neighbours queries (...

0 Julian Baldus, et al. ∙

research

∙ 03/02/2018

Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars

Tree-adjoining grammars are a generalization of context-free grammars th...

0 Karl Bringmann, et al. ∙

research

∙ 03/02/2018

Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve

Can we analyze data without decompressing it? As our data keeps growing,...

0 Amir Abboud, et al. ∙

research

∙ 10/30/2017

Approximation Algorithms for ℓ_0-Low Rank Approximation

We study the ℓ_0-Low Rank Approximation Problem, where the goal is, give...

0 Karl Bringmann, et al. ∙

Karl Bringmann

Featured Co-authors