Document Open Access Logo

Monochromatic Triangles, Intermediate Matrix Products, and Convolutions

Authors Andrea Lincoln, Adam Polak , Virginia Vassilevska Williams

PDF
Thumbnail PDF

File

LIPIcs.ITCS.2020.53.pdf
  • Filesize: 0.52 MB
  • 18 pages

Document Identifiers

Author Details

Andrea Lincoln
  • CSAIL, MIT, Cambridge, MA, USA
Adam Polak
  • Institute of Theoretical Computer Science, Faculty of Mathematics and Computer Science, Jagiellonian University, Krakow, Poland
Virginia Vassilevska Williams
  • CSAIL, MIT, Cambridge, MA, USA

Funding

  • Lincoln, Andrea: Partially supported by NSF Grant CCF-1909429.
  • Polak, Adam: Partially supported by the National Science Center, Poland under grants 2017/27/N/ ST6/01334 and 2018/28/T/ST6/00305.
  • Vassilevska Williams, Virginia: Supported by an NSF CAREER Award, NSF Grants CCF-1528078, CCF-1514339 and CCF-1909429, a BSF Grant BSF:2012338, a Google Research Fellowship and a Sloan Research Fellowship.

Acknowledgements

We would like to thank Amir Abboud for fruitful discussions at an early stage of our research. Part of the research was done when the second author was visiting MIT.

Cite AsGet BibTex

Andrea Lincoln, Adam Polak, and Virginia Vassilevska Williams. Monochromatic Triangles, Intermediate Matrix Products, and Convolutions. In 11th Innovations in Theoretical Computer Science Conference (ITCS 2020). Leibniz International Proceedings in Informatics (LIPIcs), Volume 151, pp. 53:1-53:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2020)
https://doi.org/10.4230/LIPIcs.ITCS.2020.53

Abstract

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 n^o(1) improvements over its brute-force cubic running time and is widely conjectured to require n^{3-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 Õ(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 Õ(n^2.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 n^{2-o(1)} time, the brute force running time for convolution problems. There are analogous intermediate problems that can be solved in O(n^1.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(n^1.5) time and 3SUM is in O(n^2) time (and is conjectured to require n^{2-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.

Subject Classification

ACM Subject Classification
  • Theory of computation → Problems, reductions and completeness
Keywords
  • 3SUM
  • fine-grained complexity
  • matrix multiplication
  • monochromatic triangle

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

References

  1. Amir Abboud, Fabrizio Grandoni, and Virginia Vassilevska Williams. Subcubic Equivalences Between Graph Centrality Problems, APSP and Diameter. In Proceedings of the Twenty-Sixth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2015, San Diego, CA, USA, January 4-6, 2015, pages 1681-1697, 2015. URL: https://doi.org/10.1137/1.9781611973730.112.
  2. Noga Alon, Zvi Galil, and Oded Margalit. On the Exponent of the All Pairs Shortest Path Problem. Journal of Computer and System Sciences, 54(2):255-262, 1997. URL: https://doi.org/10.1006/jcss.1997.1388.
  3. Noga Alon, Raphael Yuster, and Uri Zwick. Finding and counting given length cycles. Algorithmica, 17(3):209-223, March 1997. URL: https://doi.org/10.1007/BF02523189.
  4. Ilya Baran, Erik D. Demaine, and Mihai Pǎtraşcu. Subquadratic Algorithms for 3SUM. Algorithmica, 50(4):584-596, April 2008. URL: https://doi.org/10.1007/s00453-007-9036-3.
  5. Hodaya Barr, Tsvi Kopelowitz, Ely Porat, and Liam Roditty. -1,0,1-APSP and (min,max)-product problems, 2019. URL: http://arxiv.org/abs/1911.06132.
  6. Michael A. Bender, Giridhar Pemmasani, Steven Skiena, and Pavel Sumazin. Finding least common ancestors in directed acyclic graphs. In Proceedings of the Twelfth Annual Symposium on Discrete Algorithms, January 7-9, 2001, Washington, DC, USA., pages 845-854, 2001. URL: http://dl.acm.org/citation.cfm?id=365411.365795.
  7. David Bremner, Timothy M. Chan, Erik D. Demaine, Jeff Erickson, Ferran Hurtado, John Iacono, Stefan Langerman, and Perouz Taslakian. Necklaces, Convolutions, and X + Y. In Proceedings of the 14th Conference on Annual European Symposium - Volume 14, ESA'06, pages 160-171, London, UK, UK, 2006. Springer-Verlag. URL: https://doi.org/10.1007/11841036_17.
  8. Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. A Dichotomy for Regular Expression Membership Testing. In 58th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2017, Berkeley, CA, USA, October 15-17, 2017, pages 307-318, 2017. URL: https://doi.org/10.1109/FOCS.2017.36.
  9. Karl Bringmann and Tomasz Kociumaka. Personal communication, 2019. Google Scholar
  10. Karl Bringmann, Marvin Künnemann, and Karol Wegrzycki. Approximating APSP Without Scaling: Equivalence of Approximate Min-plus and Exact Min-max. In Proceedings of the 51st Annual ACM SIGACT Symposium on Theory of Computing, STOC 2019, pages 943-954, New York, NY, USA, 2019. ACM. URL: https://doi.org/10.1145/3313276.3316373.
  11. Timothy M. Chan. More Logarithmic-Factor Speedups for 3SUM, (median, +)-Convolution, and Some Geometric 3SUM-Hard Problems. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 881-897, 2018. URL: https://doi.org/10.1137/1.9781611975031.57.
  12. Lijie Chen and Ryan Williams. An Equivalence Class for Orthogonal Vectors. In Proceedings of the Thirtieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2019, San Diego, California, USA, January 6-9, 2019, pages 21-40, 2019. URL: https://doi.org/10.1137/1.9781611975482.2.
  13. Marek Cygan, Holger Dell, Daniel Lokshtanov, Dániel Marx, Jesper Nederlof, Yoshio Okamoto, Ramamohan Paturi, Saket Saurabh, and Magnus Wahlström. On Problems as Hard as CNF-SAT. ACM Transactions on Algorithms, 12(3):41:1-41:24, 2016. URL: https://doi.org/10.1145/2925416.
  14. Marek Cygan, Marcin Mucha, Karol Wegrzycki, and Michal Wlodarczyk. On Problems Equivalent to (Min,+)-Convolution. ACM Transactions on Algorithms, 15(1):14:1-14:25, January 2019. URL: https://doi.org/10.1145/3293465.
  15. Artur Czumaj, Mirosław Kowaluk, and Andrzej Lingas. Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theoretical Computer Science, 380(1):37-46, 2007. Automata, Languages and Programming. URL: https://doi.org/10.1016/j.tcs.2007.02.053.
  16. Artur Czumaj and Andrzej Lingas. Finding a Heaviest Triangle is Not Harder Than Matrix Multiplication. In Proceedings of the Eighteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '07, pages 986-994, Philadelphia, PA, USA, 2007. Society for Industrial and Applied Mathematics. URL: http://dl.acm.org/citation.cfm?id=1283383.1283489.
  17. Martin Dietzfelbinger. Universal hashing and k-wise independent random variables via integer arithmetic without primes. In STACS 96, pages 567-580, Berlin, Heidelberg, 1996. Springer Berlin Heidelberg. URL: https://doi.org/10.1007/3-540-60922-9_46.
  18. Ran Duan, Ce Jin, and Hongxun Wu. Faster Algorithms for All Pairs Non-Decreasing Paths Problem. In 46th International Colloquium on Automata, Languages, and Programming, ICALP 2019, July 9-12, 2019, Patras, Greece., pages 48:1-48:13, 2019. URL: https://doi.org/10.4230/LIPIcs.ICALP.2019.48.
  19. Ran Duan and Seth Pettie. Fast algorithms for (max, min)-matrix multiplication and bottleneck shortest paths. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 384-391, 2009. URL: https://doi.org/10.1137/1.9781611973068.43.
  20. Lech Duraj, Krzysztof Kleiner, Adam Polak, and Virginia Vassilevska Williams. Equivalences between triangle and range query problems. arXiv e-prints, page arXiv:1908.11819, August 2019. URL: http://arxiv.org/abs/1908.11819.
  21. Michael J Fischer and Albert R Meyer. Boolean matrix multiplication and transitive closure. In 12th Annual Symposium on Switching and Automata Theory, SWAT 1971, pages 129-131. IEEE, 1971. URL: https://doi.org/10.1109/SWAT.1971.4.
  22. Anka Gajentaan and Mark H. Overmars. On a Class of O(n²) Problems in Computational Geometry. Computational Geometry, 5:165-185, 1995. URL: https://doi.org/10.1016/0925-7721(95)00022-2.
  23. Francois Le Gall and Florent Urrutia. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. In Proceedings of the Twenty-Ninth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2018, New Orleans, LA, USA, January 7-10, 2018, pages 1029-1046, 2018. URL: https://doi.org/10.1137/1.9781611975031.67.
  24. Omer Gold and Micha Sharir. Dominance Product and High-Dimensional Closest Pair under L_∞. In Yoshio Okamoto and Takeshi Tokuyama, editors, 28th International Symposium on Algorithms and Computation (ISAAC 2017), volume 92 of Leibniz International Proceedings in Informatics (LIPIcs), pages 39:1-39:12, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ISAAC.2017.39.
  25. Allan Grønlund and Seth Pettie. Threesomes, Degenerates, and Love Triangles. Journal of the ACM, 65(4):22:1-22:25, April 2018. URL: https://doi.org/10.1145/3185378.
  26. MohammadTaghi Hajiaghayi, Silvio Lattanzi, Saeed Seddighin, and Cliff Stein. MapReduce meets fine-grained complexity: Mapreduce algorithms for APSP, matrix multiplication, 3-SUM, and beyond, 2019. URL: http://arxiv.org/abs/1905.01748.
  27. Tsvi Kopelowitz, Seth Pettie, and Ely Porat. Higher Lower Bounds from the 3SUM Conjecture. In Proceedings of the Twenty-seventh Annual ACM-SIAM Symposium on Discrete Algorithms, SODA '16, pages 1272-1287, Philadelphia, PA, USA, 2016. Society for Industrial and Applied Mathematics. URL: https://doi.org/10.1137/1.9781611974331.ch89.
  28. Marvin Künnemann, Ramamohan Paturi, and Stefan Schneider. On the Fine-Grained Complexity of One-Dimensional Dynamic Programming. In Ioannis Chatzigiannakis, Piotr Indyk, Fabian Kuhn, and Anca Muscholl, editors, 44th International Colloquium on Automata, Languages, and Programming (ICALP 2017), volume 80 of Leibniz International Proceedings in Informatics (LIPIcs), pages 21:1-21:15, Dagstuhl, Germany, 2017. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2017.21.
  29. Karim Labib, Przemyslaw Uznanski, and Daniel Wolleb-Graf. Hamming Distance Completeness. In Nadia Pisanti and Solon P. Pissis, editors, 30th Annual Symposium on Combinatorial Pattern Matching (CPM 2019), volume 128 of Leibniz International Proceedings in Informatics (LIPIcs), pages 14:1-14:17, Dagstuhl, Germany, 2019. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.CPM.2019.14.
  30. François Le Gall. Powers of Tensors and Fast Matrix Multiplication. In Proceedings of the 39th International Symposium on Symbolic and Algebraic Computation, ISSAC '14, pages 296-303, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2608628.2608664.
  31. Andrea Lincoln, Virginia Vassilevska Williams, Joshua R. Wang, and R. Ryan Williams. Deterministic Time-Space Trade-Offs for k-SUM. In 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), volume 55 of Leibniz International Proceedings in Informatics (LIPIcs), pages 58:1-58:14, Dagstuhl, Germany, 2016. Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. URL: https://doi.org/10.4230/LIPIcs.ICALP.2016.58.
  32. Jiří Matoušek. Computing Dominances in Eⁿ. Information Processing Letters, 38(5):277-278, 1991. URL: https://doi.org/10.1016/0020-0190(91)90071-O.
  33. Mihai Patrascu. Towards Polynomial Lower Bounds for Dynamic Problems. In Proceedings of the Forty-second ACM Symposium on Theory of Computing, STOC '10, pages 603-610, New York, NY, USA, 2010. ACM. URL: https://doi.org/10.1145/1806689.1806772.
  34. Raimund Seidel. On the All-Pairs-Shortest-Path Problem in Unweighted Undirected Graphs. Journal of Computer and System Sciences, 51(3):400-403, 1995. URL: https://doi.org/10.1006/jcss.1995.1078.
  35. Asaf Shapira, Raphael Yuster, and Uri Zwick. All-Pairs Bottleneck Paths in Vertex Weighted Graphs. Algorithmica, 59(4):621-633, 2011. URL: https://doi.org/10.1007/s00453-009-9328-x.
  36. Volker Strassen. Gaussian elimination is not optimal. Numerische mathematik, 13(4):354-356, 1969. URL: https://doi.org/10.1007/BF02165411.
  37. Virginia Vassilevska. Nondecreasing paths in a weighted graph or: how to optimally read a train schedule. In Proceedings of the Nineteenth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2008, San Francisco, California, USA, January 20-22, 2008, pages 465-472, 2008. URL: http://dl.acm.org/citation.cfm?id=1347082.1347133.
  38. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All-pairs bottleneck paths for general graphs in truly sub-cubic time. In Proceedings of the 39th Annual ACM Symposium on Theory of Computing, San Diego, California, USA, June 11-13, 2007, pages 585-589, 2007. URL: https://doi.org/10.1145/1250790.1250876.
  39. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. All Pairs Bottleneck Paths and Max-Min Matrix Products in Truly Subcubic Time. Theory of Computing, 5(1):173-189, 2009. URL: https://doi.org/10.4086/toc.2009.v005a009.
  40. Virginia Vassilevska, Ryan Williams, and Raphael Yuster. Finding Heaviest H-subgraphs in Real Weighted Graphs, with Applications. ACM Transactions on Algorithms, 6(3):44:1-44:23, July 2010. URL: https://doi.org/10.1145/1798596.1798597.
  41. Virginia Vassilevska Williams. Nondecreasing paths in a weighted graph or: How to optimally read a train schedule. ACM Transactions on Algorithms, 6(4):70:1-70:24, 2010. URL: https://doi.org/10.1145/1824777.1824790.
  42. Virginia Vassilevska Williams. Multiplying Matrices Faster Than Coppersmith-Winograd. In Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC '12, pages 887-898, 2012. URL: https://doi.org/10.1145/2213977.2214056.
  43. Virginia Vassilevska Williams. On some fine-grained questions in algorithms and complexity. In Proceedings of the International Congress of Mathematicians (ICM 2018), pages 3447-3487, 2018. URL: https://doi.org/10.1142/9789813272880_0188.
  44. Virginia Vassilevska Williams and R. Ryan Williams. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. Journal of the ACM, 65(5):27:1-27:38, August 2018. URL: https://doi.org/10.1145/3186893.
  45. Virginia Vassilevska Williams and Ryan Williams. Finding, Minimizing, and Counting Weighted Subgraphs. SIAM Journal on Computing, 42(3):831-854, 2013. URL: https://doi.org/10.1137/09076619X.
  46. Ryan Williams. Faster All-pairs Shortest Paths via Circuit Complexity. In Proceedings of the Forty-sixth Annual ACM Symposium on Theory of Computing, STOC '14, pages 664-673, New York, NY, USA, 2014. ACM. URL: https://doi.org/10.1145/2591796.2591811.
  47. Virginia V. Williams. Problem Set 2 in Stanford’s class CS367, Oct. 15, 2015. http://theory.stanford.edu/~virgi/cs367/hw2.pdf, 2015.
  48. J. W. Wright. The Change-Making Problem. Journal of the ACM, 22(1):125-128, January 1975. URL: https://doi.org/10.1145/321864.321874.
  49. Raphael Yuster. Efficient algorithms on sets of permutations, dominance, and real-weighted APSP. In Proceedings of the Twentieth Annual ACM-SIAM Symposium on Discrete Algorithms, SODA 2009, New York, NY, USA, January 4-6, 2009, pages 950-957, 2009. URL: https://doi.org/10.1137/1.9781611973068.103.
  50. Uri Zwick. All Pairs Shortest Paths Using Bridging Sets and Rectangular Matrix Multiplication. Journal of the ACM, 49(3):289-317, May 2002. URL: https://doi.org/10.1145/567112.567114.
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact