The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds

Cites Work

Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
Powers of tensors and fast matrix multiplication
Gaussian elimination is not optimal
Towards polynomial lower bounds for dynamic problems
Multiplying matrices faster than coppersmith-winograd
Matrix multiplication via arithmetic progressions
A new algorithm for optimal 2-constraint satisfaction and its implications
Time and tape complexity of pushdown automaton languages
General context-free recognition in less than cubic time
Fast context-free grammar parsing requires fast boolean matrix multiplication
Title not available (Why is that?)
Fast recognition of pushdown automaton and context-free languages
Finding Regular Simple Paths in Graph Databases
Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
Dynamic suffix array with polylogarithmic queries and updates
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Title not available (Why is that?)
On the complexity of set-based analysis
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
Upper and lower bounds for fully retroactive graph problems
Improved approximate pattern matching on hypertext
Pattern Matching in Hypertext
On the Complexity of String Matching for Graphs
On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
Interconvertibility of a class of set constraints and context-free-language reachability
Subcubic algorithms for recursive state machines
Faster Online Matrix-Vector Multiplication
Lengths of words accepted by nondeterministic finite automata
Tight Hardness Results for Maximum Weight Rectangles
Title not available (Why is that?)
ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
Title not available (Why is that?)
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
Upper and Lower Bounds for Dynamic Data Structures on Strings
Title not available (Why is that?)
Answering FO+MOD Queries under Updates on Bounded Degree Databases
Fine-Grained Complexity of Regular Path Queries
The dynamic \(k\)-mismatch problem
15th innovations in theoretical computer science conference (ITCS 2024), Berkeley, CA, USA, January 30 -- February 2, 2024
Simple reductions from formula-SAT to pattern matching on labeled graphs and subtree isomorphism
New bounds for matrix multiplication: from alpha to omega
A refined laser method and faster matrix multiplication
Conjunctive queries with free access patterns under updates

This page was built for publication: The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6633271)