44 citations · 115 across the 13 of their papers we have counts for
20 papers
The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
Karl Bringmann, Allan Grønlund, Marvin Künnemann +1
We pose the fine-grained hardness hypothesis that the textbook algorithm for the NFA Acceptance problem is optimal up to subpolynomial factors, even for dense NFAs and fixed alphab…
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…
Coverability in VASS Revisited: Improving Rackoff's Bound to Obtain Conditional Optimality
Marvin Künnemann, Filip Mazowiecki, Lia Schütze +2
Seminal results establish that the coverability problem for Vector Addition Systems with States (VASS) is in EXPSPACE (Rackoff, '78) and is EXPSPACE-hard already under unary encodi…
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…
Dynamic Time Warping Under Translation: Approximation Guided by Space-Filling Curves
Karl Bringmann, Sándor Kisfaludi-Bak, Marvin Künnemann +2
The Dynamic Time Warping (DTW) distance is a popular measure of similarity for a variety of sequence data. For comparing polygonal curves in , it provides a ro…
Polygon Placement Revisited: (Degree of Freedom + 1)-SUM Hardness and an Improvement via Offline Dynamic Rectangle Union
Marvin Künnemann, André Nusser
We revisit the classical problem of determining the largest copy of a simple polygon that can be placed into a simple polygon . Despite significant effort, known algorithms…
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…
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…
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…
Approximating APSP without Scaling: Equivalence of Approximate Min-Plus and Exact Min-Max
Karl Bringmann, Marvin Künnemann, Karol Węgrzycki
Zwick's -approximation algorithm for the All Pairs Shortest Path (APSP) problem runs in time , where i…
Walking the Dog Fast in Practice: Algorithm Engineering of the Fréchet Distance
Karl Bringmann, Marvin Künnemann, André Nusser
The Fréchet distance provides a natural and intuitive measure for the popular task of computing the similarity of two (polygonal) curves. While a simple algorithm computes it in ne…
Fréchet Distance Under Translation: Conditional Hardness and an Algorithm via Offline Dynamic Grid Reachability
Karl Bringmann, Marvin Künnemann, André Nusser
The discrete Fréchet distance is a popular measure for comparing polygonal curves. An important variant is the discrete Fréchet distance under translation, which enables detection…
Multivariate Fine-Grained Complexity of Longest Common Subsequence
Karl Bringmann, Marvin Künnemann
We revisit the classic combinatorial pattern matching problem of finding a longest common subsequence (LCS). For strings and of length , a textbook algorithm solves LCS…
Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-And-Solve
Amir Abboud, Arturs Backurs, Karl Bringmann +1
Can we analyze data without decompressing it? As our data keeps growing, understanding the time complexity of problems on compressed inputs, rather than in convenient uncompressed…
Tight Conditional Lower Bounds for Longest Common Increasing Subsequence
Lech Duraj, Marvin Künnemann, Adam Polak
We consider the canonical generalization of the well-studied Longest Increasing Subsequence problem to multiple sequences, called -LCIS: Given integer sequences $X_1,\dots,X…
Subquadratic Algorithms for Succinct Stable Matching
Marvin Künnemann, Daniel Moeller, Ramamohan Paturi +1
We consider the stable matching problem when the preference lists are not given explicitly but are represented in a succinct way and ask whether the problem becomes computationally…
Quadratic Conditional Lower Bounds for String Problems and Dynamic Time Warping
Karl Bringmann, Marvin Künnemann
Classic similarity measures of strings are longest common subsequence and Levenshtein distance (i.e., the classic edit distance). A classic similarity measure of curves is dynamic…
Improved approximation for Fréchet distance on c-packed curves matching conditional lower bounds
Karl Bringmann, Marvin Künnemann
The Fréchet distance is a well-studied and very popular measure of similarity of two curves. The best known algorithms have quadratic time complexity, which has recently been shown…
Quasirandom Rumor Spreading: An Experimental Analysis
Benjamin Doerr, Tobias Friedrich, Marvin Künnemann +1
We empirically analyze two versions of the well-known "randomized rumor spreading" protocol to disseminate a piece of information in networks. In the classical model, in each round…
Randomized Rounding for Routing and Covering Problems: Experiments and Improvements
Benjamin Doerr, Marvin Künnemann, Magnus Wahlström
Following previous theoretical work by Srinivasan (FOCS 2001) and the first author (STACS 2006) and a first experimental evaluation on random instances (ALENEX 2009), we investigat…