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