Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product (Q4634027): Difference between revisions

Latest revision as of 23:26, 2 August 2024

scientific article; zbMATH DE number 7051396

Language	Label	Description	Also known as
English	Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product	scientific article; zbMATH DE number 7051396

Statements

instance of

scholarly article

0 references

title

Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product (English)

0 references

zbMATH Open document ID

0 references

0 references

0 references

0 references

0 references

Virginia Vassilevska Williams

0 references

published in

SIAM Journal on Computing

0 references

publication date

7 May 2019

0 references

full work available at URL

https://arxiv.org/abs/1707.05095

0 references

Mathematics Subject Classification ID

0 references

0 references

0 references

0 references

fast matrix multiplication

0 references

min-plus product

0 references

language edit distance

0 references

RNA folding

0 references

MaRDI profile type

MaRDI publication profile

0 references

arXiv ID

1707.05095

0 references

cites work

If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser

0 references

Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter

0 references

Q4091421

0 references

A Minimum Distance Error-Correcting Parser for Context-Free Languages

0 references

Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages

0 references

On the exponent of all pairs shortest path problem

0 references

Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity

0 references

Approximating edit distance in near-linear time

0 references

Oblivious string embeddings and edit distance approximations

0 references

A nearly optimal oracle for avoiding failed vertices and edges

0 references

A faster algorithm for betweenness centrality*

0 references

Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition

0 references

More Algorithms for All-Pairs Shortest Paths in Weighted Graphs

0 references

Clustered Integer 3SUM via Additive Combinatorics

0 references

Hardness of RNA Folding Problem With Four Symbols.

0 references

Q3679225

0 references

Supersaturated graphs and hypergraphs

0 references

New Bounds on the Complexity of the Shortest Path Problem

0 references

Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions

0 references

Incremental String Comparison

0 references

Powers of tensors and fast matrix multiplication

0 references

Fast context-free grammar parsing requires fast boolean matrix multiplication

0 references

Recognizing well-parenthesized expressions in the streaming model

0 references

A faster algorithm computing string edit distances

0 references

Approximately matching context-free languages

0 references

Testing membership in parenthesis languages

0 references

An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time

0 references

On the all-pairs-shortest-path problem in unweighted undirected graphs.

0 references

Subcubic cost algorithms for the all pairs shortest path problem

0 references

Q3374243

0 references

General context-free recognition in less than cubic time

0 references

Multiplying matrices faster than coppersmith-winograd

0 references

Faster all-pairs shortest paths via circuit complexity

0 references

Q4633908

0 references

All pairs shortest paths using bridging sets and rectangular matrix multiplication

0 references

0 references

0 references

Sitelinks

Mathematics(1 entry)

mardi Publication:4634027

@@ 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 @@
+.05095
@@ Property / arXiv ID: 1707.05095 / rank @@
+Normal rank
@@ Property / cites work @@
+If the Current Clique Algorithms Are Optimal, so Is Valiant's Parser
+Normal rank
@@ Property / cites work @@
+Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter
+Normal rank
@@ Property / cites work @@
+Q4091421
@@ Property / cites work: Q4091421 / rank @@
+Normal rank
@@ Property / cites work @@
+A Minimum Distance Error-Correcting Parser for Context-Free Languages
+Normal rank
@@ Property / cites work @@
+Approximation and exact algorithms for RNA secondary structure prediction and recognition of stochastic context-free languages
+Normal rank
@@ Property / cites work @@
+On the exponent of all pairs shortest path problem
+Normal rank
@@ Property / cites work @@
+Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity
+Normal rank
@@ Property / cites work @@
+Approximating edit distance in near-linear time
@@ Property / cites work: Approximating edit distance in near-linear time / rank @@
+Normal rank
@@ Property / cites work @@
+Oblivious string embeddings and edit distance approximations
+Normal rank
@@ Property / cites work @@
+A nearly optimal oracle for avoiding failed vertices and edges
+Normal rank
@@ Property / cites work @@
+A faster algorithm for betweenness centrality*
@@ Property / cites work: A faster algorithm for betweenness centrality* / rank @@
+Normal rank
@@ Property / cites work @@
+Information Cost Tradeoffs for Augmented Index and Streaming Language Recognition
+Normal rank
@@ Property / cites work @@
+More Algorithms for All-Pairs Shortest Paths in Weighted Graphs
+Normal rank
@@ Property / cites work @@
+Clustered Integer 3SUM via Additive Combinatorics
@@ Property / cites work: Clustered Integer 3SUM via Additive Combinatorics / rank @@
+Normal rank
@@ Property / cites work @@
+Hardness of RNA Folding Problem With Four Symbols.
+Normal rank
@@ Property / cites work @@
+Q3679225
@@ Property / cites work: Q3679225 / rank @@
+Normal rank
@@ Property / cites work @@
+Supersaturated graphs and hypergraphs
@@ Property / cites work: Supersaturated graphs and hypergraphs / rank @@
+Normal rank
@@ Property / cites work @@
+New Bounds on the Complexity of the Shortest Path Problem
+Normal rank
@@ Property / cites work @@
+Streaming Algorithms for Recognizing Nearly Well-Parenthesized Expressions
+Normal rank
@@ Property / cites work @@
+Incremental String Comparison
@@ Property / cites work: Incremental String Comparison / rank @@
+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 @@
+Fast context-free grammar parsing requires fast boolean matrix multiplication
+Normal rank
@@ Property / cites work @@
+Recognizing well-parenthesized expressions in the streaming model
+Normal rank
@@ Property / cites work @@
+A faster algorithm computing string edit distances
+Normal rank
@@ Property / cites work @@
+Approximately matching context-free languages
@@ Property / cites work: Approximately matching context-free languages / rank @@
+Normal rank
@@ Property / cites work @@
+Testing membership in parenthesis languages
@@ Property / cites work: Testing membership in parenthesis languages / rank @@
+Normal rank
@@ Property / cites work @@
+An Error Correcting Parser for Context Free Grammars that Takes Less Than Cubic Time
+Normal rank
@@ Property / cites work @@
+On the all-pairs-shortest-path problem in unweighted undirected graphs.
+Normal rank
@@ Property / cites work @@
+Subcubic cost algorithms for the all pairs shortest path problem
+Normal rank
@@ Property / cites work @@
+Q3374243
@@ Property / cites work: Q3374243 / rank @@
+Normal rank
@@ Property / cites work @@
+General context-free recognition in less than cubic time
+Normal rank
@@ Property / cites work @@
+Multiplying matrices faster than coppersmith-winograd
+Normal rank
@@ Property / cites work @@
+Faster all-pairs shortest paths via circuit complexity
+Normal rank
@@ Property / cites work @@
+Q4633908
@@ Property / cites work: Q4633908 / rank @@
+Normal rank
@@ Property / cites work @@
+All pairs shortest paths using bridging sets and rectangular matrix multiplication
+Normal rank
@@ Property / OpenAlex ID @@
+W2943049588
@@ Property / OpenAlex ID: W2943049588 / rank @@
+Normal rank
@@ Property / Wikidata QID @@
+Q128022449
@@ Property / Wikidata QID: Q128022449 / rank @@
+Normal rank