The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
From MaRDI portal
Publication:6633271
Cites work
- scientific article; zbMATH DE number 3910446 (Why is no real title available?)
- scientific article; zbMATH DE number 7651219 (Why is no real title available?)
- scientific article; zbMATH DE number 7650401 (Why is no real title available?)
- 15th innovations in theoretical computer science conference (ITCS 2024), Berkeley, CA, USA, January 30 -- February 2, 2024
- A new algorithm for optimal 2-constraint satisfaction and its implications
- A refined laser method and faster matrix multiplication
- Answering FO+MOD queries under updates on bounded degree databases
- Conjunctive queries with free access patterns under updates
- Dynamic suffix array with polylogarithmic queries and updates
- Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
- Fast context-free grammar parsing requires fast Boolean matrix multiplication
- Fast recognition of pushdown automaton and context-free languages
- Faster Online Matrix-Vector Multiplication
- Finding Regular Simple Paths in Graph Databases
- Finding a heaviest vertex-weighted triangle is not harder than matrix multiplication
- Fine-Grained Complexity of Regular Path Queries
- Gaussian elimination is not optimal
- General context-free recognition in less than cubic time
- If the current clique algorithms are optimal, so is Valiant's parser
- Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
- 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
- Matrix multiplication via arithmetic progressions
- Multiplying matrices faster than coppersmith-winograd
- New bounds for matrix multiplication: from alpha to omega
- Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
- On some fine-grained questions in algorithms and complexity
- On the Complexity of String Matching for Graphs
- On the complexity of set-based analysis
- On the hardness of partially dynamic graph problems and connections to diameter
- Pattern Matching in Hypertext
- Powers of tensors and fast matrix multiplication
- Simple reductions from formula-SAT to pattern matching on labeled graphs and subtree isomorphism
- Subcubic algorithms for recursive state machines
- Subcubic equivalences between path, matrix, and triangle problems
- The dynamic \(k\)-mismatch problem
- Tight hardness for shortest cycles and paths in sparse graphs
- Tight hardness results for maximum weight rectangles
- Tighter connections between Formula-SAT and shaving logs
- Time and tape complexity of pushdown automaton languages
- Towards polynomial lower bounds for dynamic problems
- Towards unified approximate pattern matching for Hamming and \(L_1\) distance
- Unifying and strengthening hardness for dynamic problems via the online matrix-vector multiplication conjecture
- Upper and lower bounds for dynamic data structures on strings
- Upper and lower bounds for fully retroactive graph problems
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)
