44 citations · 115 across the 13 of their papers we have counts for
6 papers · 1 filter
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…
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…
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…
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…