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

DOI10.1137/17M112720XzbMath1421.68258arXiv1707.05095OpenAlexW2943049588WikidataQ128022449 ScholiaQ128022449MaRDI QIDQ4634027

Fabrizio Grandoni, Karl Bringmann, Barna Saha, Virginia Vassilevska Williams

Publication date: 7 May 2019

Published in: SIAM Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1707.05095

zbMATH Keywords

fast matrix multiplicationRNA foldingmin-plus productlanguage edit distance

Mathematics Subject Classification ID

Analysis of algorithms (68W40) Protein sequences, DNA sequences (92D20) Algorithms on strings (68W32)

Related Items (2)

From curves to words and back again: geometric computation of minimum-area homotopy ⋮ Elastic-Degenerate String Matching via Fast Matrix Multiplication

Cites Work

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

This page was built for publication: Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product