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

Cites Work

Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Unnamed Item
Upper and lower bounds for fully retroactive graph problems
Matrix multiplication via arithmetic progressions
General context-free recognition in less than cubic time
Improved approximate pattern matching on hypertext
Interconvertibility of a class of set constraints and context-free-language reachability
Lengths of words accepted by nondeterministic finite automata
Gaussian elimination is not optimal
A new algorithm for optimal 2-constraint satisfaction and its implications
Nondeterministic Extensions of the Strong Exponential Time Hypothesis and Consequences for Non-reducibility
Towards polynomial lower bounds for dynamic problems
Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
Subcubic algorithms for recursive state machines
Fast context-free grammar parsing requires fast boolean matrix multiplication
Upper and Lower Bounds for Dynamic Data Structures on Strings
Powers of tensors and fast matrix multiplication
Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
Fast recognition of pushdown automaton and context-free languages
If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
Faster Online Matrix-Vector Multiplication
On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
Tight Hardness Results for Maximum Weight Rectangles
Subcubic Equivalences Between Path, Matrix, and Triangle Problems
Finding Regular Simple Paths in Graph Databases
Pattern Matching in Hypertext
Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
Answering FO+MOD Queries under Updates on Bounded Degree Databases
ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
On the complexity of set-based analysis
Multiplying matrices faster than coppersmith-winograd
Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
Time and tape complexity of pushdown automaton languages
On the Complexity of String Matching for Graphs
Dynamic suffix array with polylogarithmic queries and updates
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
A refined laser method and faster matrix multiplication
Conjunctive queries with free access patterns under updates
New bounds for matrix multiplication: from alpha to omega

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