The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
type: Item
instance of: scholarly article
title: The NFA acceptance hypothesis: non-combinatorial and dynamic lower bounds
author: Karl Bringmann
author: Allan Grønlund
author: Marvin Künnemann
author: Kasper Green Larsen
published in: TheoretiCS
publication date: 2024-11-05T00:00:00Z
Mathematics Subject Classification ID: 68Qxx
Mathematics Subject Classification ID: 68Wxx
Mathematics Subject Classification ID: 68Pxx
zbMATH DE Number: 7939163
zbMATH Keywords: fine-grained complexity theory
zbMATH Keywords: non-deterministic finite automata
zbMATH Keywords: OMv hypothesis
zbMATH Keywords: CFL reachability
MaRDI profile type: MaRDI publication profile
cites work: If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
cites work: Q5002674
cites work: Time and tape complexity of pushdown automaton languages
cites work: A refined laser method and faster matrix multiplication
cites work: Pattern Matching in Hypertext
cites work: Tight Hardness Results for Maximum Weight Rectangles
cites work: Answering FO+MOD Queries under Updates on Bounded Degree Databases
cites work: 15th innovations in theoretical computer science conference (ITCS 2024), Berkeley, CA, USA, January 30 -- February 2, 2024
cites work: Improved Approximation for Fréchet Distance on c-packed Curves Matching Conditional Lower Bounds
cites work: Nondeterministic extensions of the strong exponential time hypothesis and consequences for non-reducibility
cites work: Fine-Grained Complexity of Regular Path Queries
cites work: Subcubic algorithms for recursive state machines
cites work: The dynamic \(k\)-mismatch problem
cites work: Upper and Lower Bounds for Dynamic Data Structures on Strings
cites work: Matrix multiplication via arithmetic progressions
cites work: Finding a Heaviest Vertex-Weighted Triangle Is not Harder than Matrix Multiplication
cites work: On the Hardness of Partially Dynamic Graph Problems and Connections to Diameter
cites work: On the Complexity of String Matching for Graphs
cites work: Towards Unified Approximate Pattern Matching for Hamming and L_1 Distance
cites work: Simple reductions from formula-SAT to pattern matching on labeled graphs and subtree isomorphism
cites work: On the complexity of set-based analysis
cites work: Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture
cites work: Upper and lower bounds for fully retroactive graph problems
cites work: Conjunctive queries with free access patterns under updates
cites work: Dynamic suffix array with polylogarithmic queries and updates
cites work: Faster Online Matrix-Vector Multiplication
cites work: Powers of tensors and fast matrix multiplication
cites work: Fast context-free grammar parsing requires fast boolean matrix multiplication
cites work: Q5875755
cites work: Q4607968
cites work: Interconvertibility of a class of set constraints and context-free-language reachability
cites work: Finding Regular Simple Paths in Graph Databases
cites work: Improved approximate pattern matching on hypertext
cites work: Q3688439
cites work: Towards polynomial lower bounds for dynamic problems
cites work: Lengths of words accepted by nondeterministic finite automata
cites work: Fast recognition of pushdown automaton and context-free languages
cites work: Q5874553
cites work: Gaussian elimination is not optimal
cites work: General context-free recognition in less than cubic time
cites work: Multiplying matrices faster than coppersmith-winograd
cites work: ON SOME FINE-GRAINED QUESTIONS IN ALGORITHMS AND COMPLEXITY
cites work: Subcubic Equivalences Between Path, Matrix, and Triangle Problems
cites work: New bounds for matrix multiplication: from alpha to omega
cites work: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm
cites work: A new algorithm for optimal 2-constraint satisfaction and its implications
DOI: 10.46298/THEORETICS.24.22
description: scientific article; zbMATH DE number 7939163