most citedThe NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds

3 citations

researchers with a paper here

Counting papers with at most 25 authors, so collaboration author lists do not stand in for the people here.

collaborating institutions
Showing cs.CCShow all

1 paper · 1 filter

cs.CC2023★ 3 cited

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…