New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Pages 935 - 943
Abstract
We revisit the fundamental Boolean Matrix Multiplication (BMM) problem. With the invention of algebraic fast matrix multiplication over 50 years ago, it also became known that BMM can be solved in truly subcubic O(nω) time, where ω<3; much work has gone into bringing ω closer to 2. Since then, a parallel line of work has sought comparably fast combinatorial algorithms but with limited success. The na'ive O(n3)-time algorithm was initially improved by a log2n factor [Arlazarov et al.; RAS’70], then by log2.25n [Bansal and Williams; FOCS’09], then by log3n [Chan; SODA’15], and finally by log4n [Yu; ICALP’15].
We design a combinatorial algorithm for BMM running in time n3 / 2Ω((logn)1/7) – a speed-up over cubic time that is stronger than any poly-log factor. This comes tantalizingly close to refuting the conjecture from the 90s that truly subcubic combinatorial algorithms for BMM are impossible. This popular conjecture is the basis for dozens of fine-grained hardness results.
Our main technical contribution is a new regularity decomposition theorem for Boolean matrices (or equivalently, bipartite graphs) under a notion of regularity that was recently introduced and analyzed analytically in the context of communication complexity [Kelley, Lovett, Meka; STOC’24], and is related to a similar notion from the recent work on 3-term arithmetic progression free sets [Kelley, Meka; FOCS’23].
References
[1]
Amir Abboud, Arturs Backurs, Karl Bringmann, and Marvin Künnemann. 2017. Fine-Grained Complexity of Analyzing Compressed Data: Quantifying Improvements over Decompress-and-Solve. In 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Chris Umans (Ed.). IEEE Computer Society, 192–203.
[2]
Amir Abboud, Karl Bringmann, and Nick Fischer. 2023. Stronger 3-SUM Lower Bounds for Approximate Distance Oracles via Additive Combinatorics. In 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Barna Saha and Rocco A. Servedio (Eds.). ACM, 391–404.
[3]
Amir Abboud, Karl Bringmann, Seri Khoury, and Or Zamir. 2022. Hardness of approximation in P via short cycle removal: Cycle detection, distance oracles, and beyond. In 54th Annual ACM Symposium on Theory of Computing (STOC 2022), Stefano Leonardi and Anupam Gupta (Eds.). ACM, 1487–1500.
[4]
Amir Abboud, Nick Fischer, and Yarin Shechter. 2024. Faster Combinatorial k-Clique Algorithms. In 16th Latin American Symposium on Theoretical Informatics (LATIN 2024) (Lecture Notes in Computer Science, Vol. 14578), José A. Soto and Andreas Wiese (Eds.). Springer, 193–206.
[5]
Amir Abboud, Loukas Georgiadis, Giuseppe F. Italiano, Robert Krauthgamer, Nikos Parotsidis, Ohad Trabelsi, Przemyslaw Uznanski, and Daniel Wolleb-Graf. 2019. Faster Algorithms for All-Pairs Bounded Min-Cuts. In 46th International Colloquium on Automata, Languages, and Programming (ICALP 2019) (LIPIcs, Vol. 132), Christel Baier, Ioannis Chatzigiannakis, Paola Flocchini, and Stefano Leonardi (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 7:1–7:15.
[6]
Amir Abboud and Nathan Wallheimer. 2023. Worst-Case to Expander-Case Reductions. In 14th Innovations in Theoretical Computer Science Conference (ITCS 2023) (LIPIcs, Vol. 251), Yael Tauman Kalai (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 1:1–1:23.
[7]
Amir Abboud and Virginia Vassilevska Williams. 2014. Popular Conjectures Imply Strong Lower Bounds for Dynamic Problems. In 55th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2014). IEEE Computer Society, 434–443.
[8]
Amir Abboud, Virginia Vassilevska Williams, and Huacheng Yu. 2018. Matching Triangles and Basing Hardness on an Extremely Popular Conjecture. SIAM J. Comput. 47, 3 (2018), 1098–1122.
[9]
Donald Aingworth, Chandra Chekuri, Piotr Indyk, and Rajeev Motwani. 1999. Fast Estimation of Diameter and Shortest Paths (Without Matrix Multiplication). SIAM J. Comput. 28, 4 (1999), 1167–1181.
[10]
Rasmus Resen Amossen and Rasmus Pagh. 2009. Faster join-projects and sparse matrix multiplications. In 12th International Conference on Database Theory (ICDT 2009) (ACM International Conference Proceeding Series, Vol. 361), Ronald Fagin (Ed.). ACM, 121–126.
[11]
Dana Angluin. 1976. The four Russians’ algorithm for Boolean matrix multiplication is optimal in its class. SIGACT News 8, 1 (1976), 29–33.
[12]
Vladimir L. Arlazarov, Yefim A. Dinic, Aleksandr Kronrod, and Igor Aleksandrovich Faradžev. 1970. On economical construction of the transitive closure of an oriented graph. In Doklady Akademii Nauk, Vol. 194. Russian Academy of Sciences, 487–488.
[13]
Nikhil Bansal and Ryan Williams. 2012. Regularity Lemmas and Combinatorial Algorithms. Theory Comput. 8, 1 (2012), 69–94.
[14]
Ilya Baran, Erik D. Demaine, and Mihai Pătraşcu. 2008. Subquadratic Algorithms for 3SUM. Algorithmica 50, 4 (2008), 584–596.
[15]
Felix A. Behrend. 1946. On Sets of Integers Which Contain No Three Terms in Arithmetical Progression. Proc. Natl. Acad. Sci. 32, 12 (1946), 331–332.
[16]
Thiago Bergamaschi, Monika Henzinger, Maximilian Probst Gutenberg, Virginia Vassilevska Williams, and Nicole Wein. 2021. New Techniques and Fine-Grained Hardness for Dynamic Near-Additive Spanners. In 32nd Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2021), Dániel Marx (Ed.). SIAM, 1836–1855.
[17]
Karl Bringmann, Nick Fischer, and Marvin Künnemann. 2019. A Fine-Grained Analogue of Schaefer’s Theorem in P: Dichotomy of ∃^k ∀-Quantified First-Order Graph Properties. In 34th Computational Complexity Conference (CCC 2019) (LIPIcs, Vol. 137), Amir Shpilka (Ed.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 31:1–31:27.
[18]
Karl Bringmann, Pawel Gawrychowski, Shay Mozes, and Oren Weimann. 2020. Tree Edit Distance Cannot be Computed in Strongly Subcubic Time (Unless APSP Can). ACM Trans. Algorithms 16, 4 (2020), 48:1–48:22.
[19]
Karl Bringmann, Allan Grønlund, and Kasper Green Larsen. 2017. A Dichotomy for Regular Expression Membership Testing. In 58th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2017), Chris Umans (Ed.). IEEE Computer Society, 307–318.
[20]
Karl Bringmann and Philip Wellnitz. 2017. Clique-Based Lower Bounds for Parsing Tree-Adjoining Grammars. In 28th Annual Symposium on Combinatorial Pattern Matching (CPM 2017) (LIPIcs, Vol. 78), Juha Kärkkäinen, Jakub Radoszewski, and Wojciech Rytter (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 12:1–12:14.
[21]
Katrin Casel and Markus L. Schmid. 2021. Fine-Grained Complexity of Regular Path Queries. In 24th International Conference on Database Theory (ICDT 2021) (LIPIcs, Vol. 186), Ke Yi and Zhewei Wei (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 19:1–19:20.
[22]
Timothy M. Chan. 2015. Speeding up the Four Russians Algorithm by About One More Logarithmic Factor. In 26th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2015), Piotr Indyk (Ed.). SIAM, 212–217.
[23]
Timothy M. Chan, Saladi Rahul, and Jie Xue. 2020. Range closest-pair search in higher dimensions. Comput. Geom. 91 (2020), 101669.
[24]
Yi-Jun Chang. 2019. Hardness of RNA folding problem with four symbols. Theor. Comput. Sci. 757 (2019), 11–26.
[25]
Raphaël Clifford, Allan Grønlund, Kasper Green Larsen, and Tatiana Starikovskaya. 2018. Upper and Lower Bounds for Dynamic Data Structures on Strings. In 35th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2018) (LIPIcs, Vol. 96), Rolf Niedermeier and Brigitte Vallée (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 22:1–22:14.
[26]
Artur Czumaj, Miroslaw Kowaluk, and Andrzej Lingas. 2007. Faster algorithms for finding lowest common ancestors in directed acyclic graphs. Theor. Comput. Sci. 380, 1-2 (2007), 37–46.
[27]
Søren Dahlgaard, Mathias Bæk Tejs Knudsen, and Morten Stöckel. 2017. Finding even cycles faster via capped k-walks. In 49th Annual ACM Symposium on Theory of Computing (STOC 2017), Hamed Hatami, Pierre McKenzie, and Valerie King (Eds.). ACM, 112–120.
[28]
Mina Dalirrooyfard, Thuy-Duong Vuong, and Virginia Vassilevska Williams. 2021. Graph Pattern Detection: Hardness for all Induced Patterns and Faster Noninduced Cycles. SIAM J. Comput. 50, 5 (2021), 1627–1662.
[29]
Debarati Das, Michal Koucký, and Michael E. Saks. 2018. Lower Bounds for Combinatorial Algorithms for Boolean Matrix Multiplication. In 35th Annual Symposium on Theoretical Aspects of Computer Science (STACS 2018) (LIPIcs, Vol. 96), Rolf Niedermeier and Brigitte Vallée (Eds.). Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 23:1–23:14.
[30]
Ran Duan, Hongxun Wu, and Renfei Zhou. 2023. Faster Matrix Multiplication via Asymmetric Hashing. In 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023). IEEE, 2129–2138.
[31]
Friedrich Eisenbrand and Fabrizio Grandoni. 2004. On the complexity of fixed parameter clique and dominating set. Theor. Comput. Sci. 326, 1-3 (2004), 57–67.
[32]
Michael J. Fischer and Albert R. Meyer. 1971. Boolean Matrix Multiplication and Transitive Closure. In 12th Annual Symposium on Switching and Automata Theory (SWAT 1971). IEEE Computer Society, 129–131.
[33]
Jacob Fox. 2011. A new proof of the graph removal lemma. Annals of Mathematics 174, 1 (2011), 561–579. issn:0003486X http://www.jstor.org/stable/23030574
[34]
Alan M. Frieze and Ravi Kannan. 1999. Quick Approximation to Matrices and Applications. Comb. 19, 2 (1999), 175–220.
[35]
Timothy W. Gowers. 1997. Lower bounds of tower type for Szemerédi’s uniformity lemma. Geometric & Functional Analysis (GAFA) 7, 2 (1997), 322–337. issn:1420-8970
[36]
Timothy W. Gowers. 2001. A new proof of Szemerédi’s theorem. Geometric & Functional Analysis (GAFA) 11 (08 2001), 465–588.
[37]
Timothy W. Gowers. 2006. Quasirandomness, Counting and Regularity for 3-Uniform Hypergraphs. Comb. Probab. Comput. 15, 1-2 (2006), 143–184.
[38]
Hamed Hatami. 2010. Graph norms and Sidorenko’s conjecture. Israel Journal of Mathematics 175, 1 (2010), 125–150. issn:1565-8511
[39]
Monika Henzinger, Sebastian Krinninger, Danupon Nanongkai, and Thatchaphol Saranurak. 2015. Unifying and Strengthening Hardness for Dynamic Problems via the Online Matrix-Vector Multiplication Conjecture. In 47th Annual ACM Symposium on Theory of Computing (STOC 2015), Rocco A. Servedio and Ronitt Rubinfeld (Eds.). ACM, 21–30.
[40]
Zhiyi Huang, Yaowei Long, Thatchaphol Saranurak, and Benyu Wang. 2023. Tight Conditional Lower Bounds for Vertex Connectivity Problems. In 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Barna Saha and Rocco A. Servedio (Eds.). ACM, 1384–1395.
[41]
Ce Jin and Yinzhan Xu. 2022. Tight dynamic problem lower bounds from generalized BMM and OMv. In 63rd Annual IEEE Symposium on Foundations of Computer Science (FOCS 2022), Stefano Leonardi and Anupam Gupta (Eds.). ACM, 1515–1528.
[42]
Ce Jin and Yinzhan Xu. 2023. Removing Additive Structure in 3SUM-Based Reductions. In 55th Annual ACM Symposium on Theory of Computing (STOC 2023), Barna Saha and Rocco A. Servedio (Eds.). ACM, 405–418.
[43]
Zander Kelley, Shachar Lovett, and Raghu Meka. 2024. Explicit separations between randomized and deterministic Number-on-Forehead communication. In 56th Annual ACM Symposium on Theory of Computing (STOC 2024). To appear. Preprint: https://arxiv.org/abs/2308.12451.
[44]
Zander Kelley and Raghu Meka. 2023. Strong Bounds for 3-Progressions. In 64th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2023). IEEE, 933–973.
[45]
Tsvi Kopelowitz, Seth Pettie, and Ely Porat. 2016. Higher Lower Bounds from the 3SUM Conjecture. In 27th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2016), Robert Krauthgamer (Ed.). SIAM, 1272–1287.
[46]
Kasper Green Larsen and R. Ryan Williams. 2017. Faster Online Matrix-Vector Multiplication. In 28th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2017), Philip N. Klein (Ed.). SIAM, 2182–2189.
[47]
Lillian Lee. 2002. Fast context-free grammar parsing requires fast boolean matrix multiplication. J. ACM 49, 1 (2002), 1–15.
[48]
Andrea Lincoln, Virginia Vassilevska Williams, and R. Ryan Williams. 2018. Tight Hardness for Shortest Cycles and Paths in Sparse Graphs. In 29th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2018), Artur Czumaj (Ed.). SIAM, 1236–1252.
[49]
JiríMatousek. 1991. Computing Dominances in Eⁿ. Inf. Process. Lett. 38, 5 (1991), 277–278.
[50]
J. Ian Munro. 1971. Efficient Determination of the Transitive Closure of a Directed Graph. Inf. Process. Lett. 1, 2 (1971), 56–58.
[51]
Jaroslav Nešetřil and Svatopluk Poljak. 1985. On the complexity of the subgraph problem. Commentationes Mathematicae Universitatis Carolinae 26, 2 (1985), 415–419.
[52]
Mihai Pătraşcu. 2010. Towards polynomial lower bounds for dynamic problems. In 42nd Annual ACM Symposium on Theory of Computing (STOC 2010), Leonard J. Schulman (Ed.). ACM, 603–610.
[53]
Liam Roditty and Uri Zwick. 2011. On Dynamic Shortest Paths Problems. Algorithmica 61, 2 (2011), 389–401.
[54]
Giorgio Satta. 1994. Tree-Adjoining Grammar Parsing and Boolean Matrix Multiplication. Comput. Linguistics 20, 2 (1994), 173–191.
[55]
Volker Strassen. 1969. Gaussian elimination is not optimal. Numer. Math. 13, 4 (1969), 354–356. issn:0945-3245
[56]
Endre Szemerédi. 1975. On sets of integers containing no k elements in arithmetic progression. Acta Arith 27, 199–245 (1975).
[57]
Leslie G. Valiant. 1975. General Context-Free Recognition in Less than Cubic Time. J. Comput. Syst. Sci. 10, 2 (1975), 308–315.
[58]
Dirk Van Gucht, Ryan Williams, David P. Woodruff, and Qin Zhang. 2015. The Communication Complexity of Distributed Set-Joins with Applications to Matrix Multiplication. In 34th ACM Symposium on Principles of Database Systems (PODS 2015), Tova Milo and Diego Calvanese (Eds.). ACM, 199–212.
[59]
Virginia Vassilevska, Ryan Williams, and Raphael Yuster. 2007. All-pairs bottleneck paths for general graphs in truly sub-cubic time. In 39th Annual ACM Symposium on Theory of Computing (STOC 2007), David S. Johnson and Uriel Feige (Eds.). ACM, 585–589.
[60]
R. Ryan Williams. 2018. Faster All-Pairs Shortest Paths via Circuit Complexity. SIAM J. Comput. 47, 5 (2018), 1965–1985.
[61]
Virginia Vassilevska Williams and R. Ryan Williams. 2018. Subcubic Equivalences Between Path, Matrix, and Triangle Problems. J. ACM 65, 5 (2018), 27:1–27:38.
[62]
Virginia Vassilevska Williams and Yinzhan Xu. 2020. Monochromatic Triangles, Triangle Listing and APSP. In 61st Annual IEEE Symposium on Foundations of Computer Science (FOCS 2020), Sandy Irani (Ed.). IEEE, 786–797.
[63]
Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2024. New Bounds for Matrix Multiplication: from Alpha to Omega. In 35th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA 2024). SIAM. To appear.
[64]
Huacheng Yu. 2018. An improved combinatorial algorithm for Boolean matrix multiplication. Inf. Comput. 261 (2018), 240–247.
[65]
Yufei Zhao. 2023. Graph Theory and Additive Combinatorics: Exploring Structure and Randomness. Cambridge University Press.
Index Terms
- New Graph Decompositions and Combinatorial Boolean Matrix Multiplication Algorithms
Recommendations
Subquadratic Algorithms for 3SUM
We obtain subquadratic algorithms for 3SUM on integers and rationals in several models. On a standard word RAM with w-bit words, we obtain a running time of $O(n^{2}/\max\{\frac{w}{\lg^{2}w},\frac{\lg^{2}n}{(\lg\lg n)^{2}}\})$ . In the circuit RAM with ...
An improved combinatorial algorithm for Boolean matrix multiplication
AbstractWe present a new combinatorial algorithm for triangle finding and Boolean matrix multiplication that runs in O ˆ ( n 3 / log 4 n ) time, where the O ˆ notation suppresses poly(loglog) factors. This improves the previous best ...
A Fast Output-Sensitive Algorithm for Boolean Matrix Multiplication
We use randomness to exploit the potential sparsity of the Boolean matrix product in order to speed up the computation of the product. Our new fast output-sensitive algorithm for Boolean matrix product and its witnesses is randomized and provides the ...
Comments
Please enable JavaScript to view thecomments powered by Disqus.Information & Contributors
Information
Published In
June 2024
2049 pages
ISBN:9798400703836
DOI:10.1145/3618260
- General Chairs:
- Bojan Mohar,
- Igor Shinkar,
- Program Chair:
- Ryan O'Donnell
Copyright © 2024 Owner/Author.
This work is licensed under a Creative Commons Attribution International 4.0 License.
Sponsors
Publisher
Association for Computing Machinery
New York, NY, United States
Publication History
Published: 11 June 2024
Check for updates
Author Tags
Qualifiers
- Research-article
Conference
STOC '24
Sponsor:
Acceptance Rates
Overall Acceptance Rate 1,469 of 4,586 submissions, 32%
Contributors
Other Metrics
Bibliometrics & Citations
Bibliometrics
Article Metrics
- 0Total Citations
- 160Total Downloads
- Downloads (Last 12 months)160
- Downloads (Last 6 weeks)73
Reflects downloads up to 28 Sep 2024
Other Metrics
Citations
View Options
Get Access
Login options
Check if you have access through your login credentials or your institution to get full access on this article.
Sign in