If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser (Q4562283): Difference between revisions

@@ Property / author @@
-Virginia Vassilevska Williams
@@ Property / author: Virginia Vassilevska Williams / rank @@
-Normal rank
@@ Property / author @@
+Virginia Vassilevska Williams
@@ Property / author: Virginia Vassilevska Williams / rank @@
+Normal rank
@@ Property / MaRDI profile type @@
+MaRDI publication profile
@@ Property / MaRDI profile type: MaRDI publication profile / rank @@
+Normal rank
@@ Property / arXiv ID @@
+.01431
@@ Property / arXiv ID: 1504.01431 / rank @@
+Normal rank
@@ Property / cites work @@
+Losing Weight by Gaining Edges
@@ Property / cites work: Losing Weight by Gaining Edges / rank @@
+Normal rank
@@ Property / cites work @@
+A Minimum Distance Error-Correcting Parser for Context-Free Languages
+Normal rank
@@ Property / cites work @@
+Q5452362
@@ Property / cites work: Q5452362 / rank @@
+Normal rank
@@ Property / cites work @@
+Q4249533
@@ Property / cites work: Q4249533 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3549649
@@ Property / cites work: Q3549649 / rank @@
+Normal rank
@@ Property / cites work @@
+The monotone circuit complexity of Boolean functions
+Normal rank
@@ Property / cites work @@
+Q4705344
@@ Property / cites work: Q4705344 / rank @@
+Normal rank
@@ Property / cites work @@
+Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
+Normal rank
@@ Property / cites work @@
+Sparse RNA folding: time and space efficient algorithms
+Normal rank
@@ Property / cites work @@
+Edit Distance Cannot Be Computed in Strongly Subquadratic Time (unless SETH is false)
+Normal rank
@@ Property / cites work @@
+Q5110876
@@ Property / cites work: Q5110876 / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness of RNA Folding Problem With Four Symbols.
+Normal rank
@@ Property / cites work @@
+Tight lower bounds for certain parameterized NP-hard problems
+Normal rank
@@ Property / cites work @@
+Strong computational lower bounds via parameterized complexity
+Normal rank
@@ Property / cites work @@
+On certain formal properties of grammars
@@ Property / cites work: On certain formal properties of grammars / rank @@
+Normal rank
@@ Property / cites work @@
+Q5657644
@@ Property / cites work: Q5657644 / rank @@
+Normal rank
@@ Property / cites work @@
+Q3651735
@@ Property / cites work: Q3651735 / rank @@
+Normal rank
@@ Property / cites work @@
+Biological Sequence Analysis
@@ Property / cites work: Biological Sequence Analysis / rank @@
+Normal rank
@@ Property / cites work @@
+An efficient context-free parsing algorithm
@@ Property / cites work: An efficient context-free parsing algorithm / rank @@
+Normal rank
@@ Property / cites work @@
+On the complexity of fixed parameter clique and dominating set
+Normal rank
@@ Property / cites work @@
+On the role of error productions in syntactic error correction
+Normal rank
@@ Property / cites work @@
+Powers of tensors and fast matrix multiplication
@@ Property / cites work: Powers of tensors and fast matrix multiplication / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition time of context-free languages by on-line Turing machines
+Normal rank
@@ Property / cites work @@
+An Improved Context-Free Recognizer
@@ Property / cites work: An Improved Context-Free Recognizer / rank @@
+Normal rank
@@ Property / cites work @@
+On the Computational Complexity of Algorithms
@@ Property / cites work: On the Computational Complexity of Algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Clique is hard to approximate within \(n^{1-\epsilon}\)
+Normal rank
@@ Property / cites work @@
+On the Parsing of Deterministic Languages
@@ Property / cites work: On the Parsing of Deterministic Languages / rank @@
+Normal rank
@@ Property / cites work @@
+How Hard Is It to Approximate the Best Nash Equilibrium?
+Normal rank
@@ Property / cites work @@
+Q4506483
@@ Property / cites work: Q4506483 / rank @@
+Normal rank
@@ Property / cites work @@
+Large Cliques Elude the Metropolis Process
@@ Property / cites work: Large Cliques Elude the Metropolis Process / rank @@
+Normal rank
@@ Property / cites work @@
+Reducibility among Combinatorial Problems
@@ Property / cites work: Reducibility among Combinatorial Problems / rank @@
+Normal rank
@@ Property / cites work @@
+On the translation of languages from left to right
+Normal rank
@@ Property / cites work @@
+Q4054657
@@ Property / cites work: Q4054657 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast context-free grammar parsing requires fast boolean matrix multiplication
+Normal rank
@@ Property / cites work @@
+Approximately matching context-free languages
@@ Property / cites work: Approximately matching context-free languages / rank @@
+Normal rank
@@ Property / cites work @@
+Q3688439
@@ Property / cites work: Q3688439 / rank @@
+Normal rank
@@ Property / cites work @@
+Edit Distance with Duplications and Contractions Revisited
+Normal rank
@@ Property / cites work @@
+An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time
+Normal rank
@@ Property / cites work @@
+Q4197337
@@ Property / cites work: Q4197337 / rank @@
+Normal rank
@@ Property / cites work @@
+Fast recognition of pushdown automaton and context-free languages
+Normal rank
@@ Property / cites work @@
+Context-free recognition via shortest paths computation: a version of Valiant's algorithm
+Normal rank
@@ Property / cites work @@
+A simplified lower bound for context-free-language recognition
+Normal rank
@@ Property / cites work @@
+Q3392275
@@ Property / cites work: Q3392275 / rank @@
+Normal rank
@@ Property / cites work @@
+Gaussian elimination is not optimal
@@ Property / cites work: Gaussian elimination is not optimal / rank @@
+Normal rank
@@ Property / cites work @@
+General context-free recognition in less than cubic time
+Normal rank
@@ Property / cites work @@
+Efficient algorithms for clique problems
@@ Property / cites work: Efficient algorithms for clique problems / rank @@
+Normal rank
@@ Property / cites work @@
+A new algorithm for optimal 2-constraint satisfaction and its implications
+Normal rank
@@ Property / cites work @@
+Faster all-pairs shortest paths via circuit complexity
+Normal rank
@@ Property / cites work @@
+Multiplying matrices faster than coppersmith-winograd
+Normal rank
@@ Property / cites work @@
+Parameterized and Exact Computation
@@ Property / cites work: Parameterized and Exact Computation / rank @@
+Normal rank
@@ Property / cites work @@
+Open problems around exact algorithms
@@ Property / cites work: Open problems around exact algorithms / rank @@
+Normal rank
@@ Property / cites work @@
+Recognition and parsing of context-free languages in time n3
+Normal rank
@@ Property / cites work @@
+An improved combinatorial algorithm for Boolean matrix multiplication
+Normal rank
@@ Property / OpenAlex ID @@
+W2905173192
@@ Property / OpenAlex ID: W2905173192 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q128719284
@@ Property / Wikidata QID: Q128719284 / rank @@
+Normal rank