8 citations · 14 across the 11 of their papers we have counts for
13 papers · 1 filter
Robustifying Sparse Matrix Multiplication
Karl Bringmann, Nick Fischer, Vasileios Nakos
In the seminal sparse matrix multiplication problem the goal is to compute the product of two matrices when the matrices are sparse, i.e., when the number of nonzeros…
Beating Bellman's Algorithm for Subset Sum
Karl Bringmann, Nick Fischer, Vasileios Nakos
Bellman's algorithm for Subset Sum is one of the earliest and simplest examples of dynamic programming, dating back to 1957. For a given set of integers and a target , i…
Faster Sublinear-Time Edit Distance
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We study the fundamental problem of approximating the edit distance of two strings. After an extensive line of research led to the development of a constant-factor approximation al…
The Time Complexity of Fully Sparse Matrix Multiplication
Amir Abboud, Karl Bringmann, Nick Fischer +1
What is the time complexity of matrix multiplication of sparse integer matrices with nonzeros in the input and nonzeros in the output? This paper provides improv…
Negative-Weight Single-Source Shortest Paths in Near-Linear Time: Now Faster!
Karl Bringmann, Alejandro Cassis, Nick Fischer
In this work we revisit the fundamental Single-Source Shortest Paths (SSSP) problem with possibly negative edge weights. A recent breakthrough result by Bernstein, Nanongkai and Wu…
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…
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…
Almost-Optimal Sublinear-Time Edit Distance in the Low Distance Regime
Karl Bringmann, Alejandro Cassis, Nick Fischer +1
We revisit the task of computing the edit distance in sublinear time. In the -gap edit distance problem the task is to distinguish whether the edit distance of two strings i…
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…
Sparse Nonnegative Convolution Is Equivalent to Dense Nonnegative Convolution
Karl Bringmann, Nick Fischer, Vasileios Nakos
Computing the convolution of two length- vectors is an ubiquitous computational primitive. Applications range from string problems to Knapsack-type problems, an…
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…