In this video, I present a paper from the ITCS'24: Innovations in Theoretical Computer Science conference. The main contribution of the work is to introduce a new hardness conjecture to the landscape of fine-grained complexity. The conjecture asserts that the naive algorithm is optimal for determining whether a given string is accepted by a Nondeterministic Finite Automata. Using this conjecture, we show hardness of numerous dynamic problems via a reduction to the Online Matrix Vector Multiplication problem. We also show that the new conjecture implies tight lower bounds for numerous problems where we only had combinatorial lower bounds before.
Негізгі бет The NFA Acceptance Hypothesis: Non-Combinatorial and Dynamic Lower Bounds
Пікірлер