If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
From MaRDI portal
Publication:4562283
DOI10.1137/16M1061771zbMath1412.68094arXiv1504.01431OpenAlexW2905173192WikidataQ128719284 ScholiaQ128719284MaRDI QIDQ4562283
Artūrs Bačkurs, Amir Abboud, Virginia Vassilevska Williams
Publication date: 19 December 2018
Published in: SIAM Journal on Computing (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1504.01431
context-free grammarscombinatorial algorithmsRNA foldinghardness in PDyck edit distanceconditional lower boundsCFG parsingclique algorithmsValiant's algorithm
Analysis of algorithms and problem complexity (68Q25) Formal languages and automata (68Q45) Protein sequences, DNA sequences (92D20) Grammars and rewriting systems (68Q42) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)
Related Items
Complexity of Searching for 2 by 2 Submatrices in Boolean Matrices, A linear-time simulation of deterministic \(d\)-limited automata, On minimizing regular expressions without Kleene star, Pushdown reachability with constant treewidth, Unnamed Item, Fine-Grained Complexity of Regular Path Queries, Improved Merlin-Arthur protocols for central problems in fine-grained complexity, On Approximating the Number of $k$-Cliques in Sublinear Time, Fooling views: a new lower bound technique for distributed computations under congestion, Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product, Work-sensitive dynamic complexity of formal languages, Algorithms and conditional lower bounds for planning problems, Unnamed Item, Unnamed Item, Unnamed Item, Computing the depth distribution of a set of boxes, A fine-grained analogue of schaefer's Theorem in P: dichotomy of ∃k∀-quantified first-order graph properties, Fine-Grained Complexity Theory (Tutorial), Finding small satisfying assignments faster than brute force: a fine-grained perspective into boolean constraint satisfaction, Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles, Unnamed Item, Elastic-Degenerate String Matching via Fast Matrix Multiplication
Cites Work
- Sparse RNA folding: time and space efficient algorithms
- Context-free recognition via shortest paths computation: a version of Valiant's algorithm
- Approximately matching context-free languages
- On the complexity of fixed parameter clique and dominating set
- Strong computational lower bounds via parameterized complexity
- Efficient algorithms for clique problems
- The monotone circuit complexity of Boolean functions
- General context-free recognition in less than cubic time
- Clique is hard to approximate within \(n^{1-\epsilon}\)
- An improved combinatorial algorithm for Boolean matrix multiplication
- Open problems around exact algorithms
- Gaussian elimination is not optimal
- Tight lower bounds for certain parameterized NP-hard problems
- A new algorithm for optimal 2-constraint satisfaction and its implications
- An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time
- Losing Weight by Gaining Edges
- Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
- How Hard Is It to Approximate the Best Nash Equilibrium?
- Edit Distance with Duplications and Contractions Revisited
- Fast context-free grammar parsing requires fast boolean matrix multiplication
- On certain formal properties of grammars
- Powers of tensors and fast matrix multiplication
- A simplified lower bound for context-free-language recognition
- Fast recognition of pushdown automaton and context-free languages
- On the role of error productions in syntactic error correction
- An Improved Context-Free Recognizer
- Large Cliques Elude the Metropolis Process
- On the Parsing of Deterministic Languages
- Biological Sequence Analysis
- Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
- Reducibility among Combinatorial Problems
- Faster all-pairs shortest paths via circuit complexity
- Parameterized and Exact Computation
- On the Computational Complexity of Algorithms
- Hardness of RNA Folding Problem With Four Symbols.
- Multiplying matrices faster than coppersmith-winograd
- Recognition and parsing of context-free languages in time n3
- An efficient context-free parsing algorithm
- Recognition time of context-free languages by on-line Turing machines
- On the translation of languages from left to right
- A Minimum Distance Error-Correcting Parser for Context-Free Languages
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
