Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product
© 2019 Society for Industrial and Applied Mathematics It is a major open problem whether the (min, +)-product of two n × n matrices has a truly subcubic (i.e., O(n3−ε) for ε > 0) time algorithm; in particular, since it is equivalent to the famous all-pairs-shortest-paths problem (APSP) in n-verte...
| Main Authors: | , , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
Society for Industrial & Applied Mathematics (SIAM)
2021
|
| Online Access: | https://hdl.handle.net/1721.1/136191 |
| _version_ | 1826204797259218944 |
|---|---|
| author | Bringmann, Karl Grandoni, Fabrizio Saha, Barna Williams, Virginia Vassilevska |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Bringmann, Karl Grandoni, Fabrizio Saha, Barna Williams, Virginia Vassilevska |
| author_sort | Bringmann, Karl |
| collection | MIT |
| description | © 2019 Society for Industrial and Applied Mathematics It is a major open problem whether the (min, +)-product of two n × n matrices has a truly subcubic (i.e., O(n3−ε) for ε > 0) time algorithm; in particular, since it is equivalent to the famous all-pairs-shortest-paths problem (APSP) in n-vertex graphs. Some restrictions of the (min, +)-product to special types of matrices are known to admit truly subcubic algorithms, each giving rise to a special case of APSP that can be solved faster. In this paper we consider a new, different, and powerful restriction in which all matrix entries are integers and one matrix can be arbitrary, as long as the other matrix has “bounded differences” in either its columns or rows, i.e., any two consecutive entries differ by only a small amount. We obtain the first truly subcubic algorithm for this bounded-difference (min, +)-product (answering an open problem of Chan and Lewenstein). Our new algorithm, combined with a strengthening of an approach of Valiant for solving context-free grammar parsing with matrix multiplication, yields the first truly subcubic algorithms for the following problems: language edit distance (a major problem in the parsing community), RNA folding (a major problem in bioinformatics), and optimum stack generation (answering an open problem of Tarjan). |
| first_indexed | 2024-09-23T13:01:14Z |
| format | Article |
| id | mit-1721.1/136191 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T13:01:14Z |
| publishDate | 2021 |
| publisher | Society for Industrial & Applied Mathematics (SIAM) |
| record_format | dspace |
| spelling | mit-1721.1/1361912023-12-12T16:08:20Z Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product Bringmann, Karl Grandoni, Fabrizio Saha, Barna Williams, Virginia Vassilevska Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © 2019 Society for Industrial and Applied Mathematics It is a major open problem whether the (min, +)-product of two n × n matrices has a truly subcubic (i.e., O(n3−ε) for ε > 0) time algorithm; in particular, since it is equivalent to the famous all-pairs-shortest-paths problem (APSP) in n-vertex graphs. Some restrictions of the (min, +)-product to special types of matrices are known to admit truly subcubic algorithms, each giving rise to a special case of APSP that can be solved faster. In this paper we consider a new, different, and powerful restriction in which all matrix entries are integers and one matrix can be arbitrary, as long as the other matrix has “bounded differences” in either its columns or rows, i.e., any two consecutive entries differ by only a small amount. We obtain the first truly subcubic algorithm for this bounded-difference (min, +)-product (answering an open problem of Chan and Lewenstein). Our new algorithm, combined with a strengthening of an approach of Valiant for solving context-free grammar parsing with matrix multiplication, yields the first truly subcubic algorithms for the following problems: language edit distance (a major problem in the parsing community), RNA folding (a major problem in bioinformatics), and optimum stack generation (answering an open problem of Tarjan). 2021-10-27T20:34:11Z 2021-10-27T20:34:11Z 2019 2019-07-09T13:59:07Z Article http://purl.org/eprint/type/JournalArticle https://hdl.handle.net/1721.1/136191 en 10.1137/17M112720X SIAM Journal on Computing Article is made available in accordance with the publisher's policy and may be subject to US copyright law. Please refer to the publisher's site for terms of use. application/pdf Society for Industrial & Applied Mathematics (SIAM) SIAM |
| spellingShingle | Bringmann, Karl Grandoni, Fabrizio Saha, Barna Williams, Virginia Vassilevska Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product |
| title | Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product |
| title_full | Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product |
| title_fullStr | Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product |
| title_full_unstemmed | Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product |
| title_short | Truly Subcubic Algorithms for Language Edit Distance and RNA Folding via Fast Bounded-Difference Min-Plus Product |
| title_sort | truly subcubic algorithms for language edit distance and rna folding via fast bounded difference min plus product |
| url | https://hdl.handle.net/1721.1/136191 |
| work_keys_str_mv | AT bringmannkarl trulysubcubicalgorithmsforlanguageeditdistanceandrnafoldingviafastboundeddifferenceminplusproduct AT grandonifabrizio trulysubcubicalgorithmsforlanguageeditdistanceandrnafoldingviafastboundeddifferenceminplusproduct AT sahabarna trulysubcubicalgorithmsforlanguageeditdistanceandrnafoldingviafastboundeddifferenceminplusproduct AT williamsvirginiavassilevska trulysubcubicalgorithmsforlanguageeditdistanceandrnafoldingviafastboundeddifferenceminplusproduct |