Monochromatic triangles, intermediate matrix products, and convolutions
© Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(nω) time algorithms for ω < 2.373. On the other hand, the (min, +) matrix product which is at the heart of many fundamental graph problems s...
| Main Authors: | , , |
|---|---|
| Other Authors: | |
| Format: | Article |
| Language: | English |
| Published: |
2021
|
| Online Access: | https://hdl.handle.net/1721.1/137443 |
| _version_ | 1826213010377539584 |
|---|---|
| author | Williams, Virginia Vassilevska Polak, Adam Lincoln, Andrea |
| author2 | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory |
| author_facet | Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory Williams, Virginia Vassilevska Polak, Adam Lincoln, Andrea |
| author_sort | Williams, Virginia Vassilevska |
| collection | MIT |
| description | © Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(nω) time algorithms for ω < 2.373. On the other hand, the (min, +) matrix product which is at the heart of many fundamental graph problems such as All-Pairs Shortest Paths, has received only minor no(1) improvements over its brute-force cubic running time and is widely conjectured to require n3−o(1) time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems. For instance, the Min-Max matrix product, the Minimum Witness matrix product, All-Pairs Shortest Paths in directed unweighted graphs and determining whether an edge-colored graph contains a monochromatic triangle, can all be solved in Oe(n(3+ω)/2) time. While slight improvements are sometimes possible using rectangular matrix multiplication, if ω = 2, the best runtimes for these “intermediate” problems are all Oe(n2.5). A similar phenomenon occurs for convolution problems. Here, using the FFT, the usual (+, ×)- convolution of two n-length sequences can be solved in O(n log n) time, while the (min, +) convolution is conjectured to require n2−o(1) time, the brute force running time for convolution problems. There are analogous intermediate problems that can be solved in O(n1.5) time, but seemingly not much faster: Min-Max convolution, Minimum Witness convolution, etc. Can one improve upon the running times for these intermediate problems, in either the matrix product or the convolution world? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way? This paper makes progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and Minimum Witness product can be reduced to both the Min-Max product and a variant of the monochromatic triangle problem, so that a significant improvement over n(3+ω)/2 time for any of the latter problems would result in a similar improvement for both of the former problems. We also show that a natural convolution variant of monochromatic triangle is fine-grained equivalent to the famous 3SUM problem. As this variant is solvable in O(n1.5) time and 3SUM is in O(n2) time (and is conjectured to require n2−o(1) time), our result gives the first fine-grained equivalence between natural problems of different running times. We also relate 3SUM to monochromatic triangle, and a coin change problem to monochromatic convolution, and thus to 3SUM. |
| first_indexed | 2024-09-23T15:41:41Z |
| format | Article |
| id | mit-1721.1/137443 |
| institution | Massachusetts Institute of Technology |
| language | English |
| last_indexed | 2024-09-23T15:41:41Z |
| publishDate | 2021 |
| record_format | dspace |
| spelling | mit-1721.1/1374432023-04-20T19:29:17Z Monochromatic triangles, intermediate matrix products, and convolutions Williams, Virginia Vassilevska Polak, Adam Lincoln, Andrea Massachusetts Institute of Technology. Computer Science and Artificial Intelligence Laboratory © Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. The most studied linear algebraic operation, matrix multiplication, has surprisingly fast O(nω) time algorithms for ω < 2.373. On the other hand, the (min, +) matrix product which is at the heart of many fundamental graph problems such as All-Pairs Shortest Paths, has received only minor no(1) improvements over its brute-force cubic running time and is widely conjectured to require n3−o(1) time. There is a plethora of matrix products and graph problems whose complexity seems to lie in the middle of these two problems. For instance, the Min-Max matrix product, the Minimum Witness matrix product, All-Pairs Shortest Paths in directed unweighted graphs and determining whether an edge-colored graph contains a monochromatic triangle, can all be solved in Oe(n(3+ω)/2) time. While slight improvements are sometimes possible using rectangular matrix multiplication, if ω = 2, the best runtimes for these “intermediate” problems are all Oe(n2.5). A similar phenomenon occurs for convolution problems. Here, using the FFT, the usual (+, ×)- convolution of two n-length sequences can be solved in O(n log n) time, while the (min, +) convolution is conjectured to require n2−o(1) time, the brute force running time for convolution problems. There are analogous intermediate problems that can be solved in O(n1.5) time, but seemingly not much faster: Min-Max convolution, Minimum Witness convolution, etc. Can one improve upon the running times for these intermediate problems, in either the matrix product or the convolution world? Or, alternatively, can one relate these problems to each other and to other key problems in a meaningful way? This paper makes progress on these questions by providing a network of fine-grained reductions. We show for instance that APSP in directed unweighted graphs and Minimum Witness product can be reduced to both the Min-Max product and a variant of the monochromatic triangle problem, so that a significant improvement over n(3+ω)/2 time for any of the latter problems would result in a similar improvement for both of the former problems. We also show that a natural convolution variant of monochromatic triangle is fine-grained equivalent to the famous 3SUM problem. As this variant is solvable in O(n1.5) time and 3SUM is in O(n2) time (and is conjectured to require n2−o(1) time), our result gives the first fine-grained equivalence between natural problems of different running times. We also relate 3SUM to monochromatic triangle, and a coin change problem to monochromatic convolution, and thus to 3SUM. 2021-11-05T12:57:08Z 2021-11-05T12:57:08Z 2020 2021-03-22T16:57:48Z Article http://purl.org/eprint/type/ConferencePaper https://hdl.handle.net/1721.1/137443 Williams, Virginia Vassilevska, Polak, Adam and Lincoln, Andrea. 2020. "Monochromatic triangles, intermediate matrix products, and convolutions." Leibniz International Proceedings in Informatics, LIPIcs, 151. en 10.4230/LIPIcs.ITCS.2020.53 Leibniz International Proceedings in Informatics, LIPIcs Creative Commons Attribution 4.0 International license https://creativecommons.org/licenses/by/4.0/ application/pdf DROPS |
| spellingShingle | Williams, Virginia Vassilevska Polak, Adam Lincoln, Andrea Monochromatic triangles, intermediate matrix products, and convolutions |
| title | Monochromatic triangles, intermediate matrix products, and convolutions |
| title_full | Monochromatic triangles, intermediate matrix products, and convolutions |
| title_fullStr | Monochromatic triangles, intermediate matrix products, and convolutions |
| title_full_unstemmed | Monochromatic triangles, intermediate matrix products, and convolutions |
| title_short | Monochromatic triangles, intermediate matrix products, and convolutions |
| title_sort | monochromatic triangles intermediate matrix products and convolutions |
| url | https://hdl.handle.net/1721.1/137443 |
| work_keys_str_mv | AT williamsvirginiavassilevska monochromatictrianglesintermediatematrixproductsandconvolutions AT polakadam monochromatictrianglesintermediatematrixproductsandconvolutions AT lincolnandrea monochromatictrianglesintermediatematrixproductsandconvolutions |