{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,10,16]],"date-time":"2026-10-16T07:45:59Z","timestamp":1792136759064,"version":"4.4.0"},"reference-count":38,"publisher":"Association for Computing Machinery (ACM)","issue":"2","funder":[{"DOI":"10.13039\/501100006374","name":"NSF","doi-asserted-by":"publisher","award":["NSF-BSF 2109922, NSF-IIS 2314527, NSF-SHF 2312195"],"award-info":[{"award-number":["NSF-BSF 2109922, NSF-IIS 2314527, NSF-SHF 2312195"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Simons Institute for the Theory of Computing, University of California Berkeley","doi-asserted-by":"publisher","award":["Fall 2023 Program on Logic and Algorithms in Database Theory and AI"],"award-info":[{"award-number":["Fall 2023 Program on Logic and Algorithms in Database Theory and AI"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100006374","name":"Natural Sciences and Engineering Research Council of Canada","doi-asserted-by":"publisher","award":["Discovery Grant"],"award-info":[{"award-number":["Discovery Grant"]}],"id":[{"id":"10.13039\/501100006374","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. ACM Manag. Data"],"published-print":{"date-parts":[[2025,6,9]]},"abstract":"<jats:p>\n            One fundamental question in database theory is the following: Given a Boolean conjunctive query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            , what is the best complexity for computing the answer to Q in terms of the input database size\n            <jats:italic toggle=\"yes\">N<\/jats:italic>\n            ? When restricted to the class of combinatorial algorithms, it is known that the best known complexity for any query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            is captured by the\n            <jats:italic toggle=\"yes\">submodular width<\/jats:italic>\n            of\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            . However, beyond combinatorial algorithms, certain queries are known to admit faster algorithms that often involve a clever combination of fast matrix multiplication and data partitioning. Nevertheless, there is no systematic way to derive and analyze the complexity of such algorithms for arbitrary queries\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            .\n          <\/jats:p>\n          <jats:p>\n            In this work, we introduce a general framework that captures the best complexity for answering any Boolean conjunctive query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            using matrix multiplication. Our framework unifies both combinatorial and non-combinatorial techniques under the umbrella of information theory. It generalizes the notion of submodular width to a new stronger notion called the \u03c9-\n            <jats:italic toggle=\"yes\">submodular width<\/jats:italic>\n            that naturally incorporates the power of fast matrix multiplication. We describe a matching algorithm that computes the answer to any query\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            in time corresponding to the \u03c9-\n            <jats:italic toggle=\"yes\">submodular<\/jats:italic>\n            width of\n            <jats:italic toggle=\"yes\">Q<\/jats:italic>\n            . We show that our framework recovers the best known complexities for Boolean queries that have been studied in the literature, to the best of our knowledge, and also discovers new algorithms for some classes of queries that improve upon the best known complexities.\n          <\/jats:p>","DOI":"10.1145\/3725235","type":"journal-article","created":{"date-parts":[[2025,6,9]],"date-time":"2025-06-09T15:20:31Z","timestamp":1749482431000},"page":"1-26","source":"Crossref","is-referenced-by-count":5,"title":["Fast Matrix Multiplication meets the Submodular Width"],"prefix":"10.1145","volume":"3","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-3894-6494","authenticated-orcid":false,"given":"Mahmoud","family":"Abo Khamis","sequence":"first","affiliation":[{"name":"Query Optimizer, RelationalAI, Berkeley, CA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-7890-665X","authenticated-orcid":false,"given":"Xiao","family":"Hu","sequence":"additional","affiliation":[{"name":"Cheriton School of Computer Science, University of Waterloo, Waterloo, ON, Canada"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-4144-0868","authenticated-orcid":false,"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"Department of Computer Science &amp; Engineering, University of Washington, Seattle, WA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,9]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.167"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3426865"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2412.06189"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2902251.2902280"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3034786.3056105"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.48550\/arXiv.2402.02001"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02523189"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1514894.1514909"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2008.43"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/110859440"},{"key":"e_1_2_1_11_1","volume-title":"51st International Colloquium on Automata, Languages, and Programming (ICALP","author":"Censor-Hillel Keren","year":"2024","unstructured":"Keren Censor-Hillel, Tomer Even, and Virginia Vassilevska Williams. 2024. Fast Approximate Counting of Cycles. In 51st International Colloquium on Automata, Languages, and Programming (ICALP 2024). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 37--1."},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3618260.3649663"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316329"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0004--3702(99)00059--4"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1007\/978--3-031-01583-0"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3318464.3380607"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2004.05.009"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","unstructured":"Francois Le Gall and Florent Urrutia. [n. d.]. Improved Rectangular Matrix Multiplication using Powers of the Coppersmith-Winograd Tensor. 1029--1046. doi:10.1137\/1.9781611975031.67 arXiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611975031.67","DOI":"10.1137\/1.9781611975031.67"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.5555\/1109557.1109590"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2636918"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3651599"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.14778\/3547305.3547326"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611978322.6"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977936.3"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2535926"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/3196959.3196990"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3180143"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2590989.2590991"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806772"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF02165411"},{"key":"e_1_2_1_31_1","volume-title":"49th International Colloquium on Automata, Languages, and Programming (ICALP","author":"T\u011btek Jakub","year":"2022","unstructured":"Jakub T\u011btek. 2022. Approximate Triangle Counting via Sampling and Fast Matrix Multiplication. In 49th International Colloquium on Automata, Languages, and Programming (ICALP 2022). Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, 107--1."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.5441\/002\/icdt.2014.13"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","unstructured":"Virginia Vassilevska Williams Yinzhan Xu Zixuan Xu and Renfei Zhou. [n. d.]. New Bounds for Matrix Multiplication: from Alpha to Omega. 3792--3835. doi:10.1137\/1.9781611977912.134 arXiv:https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/1.9781611977912.134","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611977912.134"},{"key":"e_1_2_1_35_1","volume-title":"7th International Conference, September 9--11","author":"Yannakakis Mihalis","year":"1981","unstructured":"Mihalis Yannakakis. 1981. Algorithms for Acyclic Database Schemes. In Very Large Data Bases, 7th International Conference, September 9--11, 1981, Cannes, France, Proceedings. IEEE Computer Society, 82--94."},{"key":"e_1_2_1_36_1","first-page":"254","article-title":"Detecting short directed cycles using rectangular matrix multiplication and dynamic programming","volume":"4","author":"Yuster Raphael","year":"2004","unstructured":"Raphael Yuster and Uri Zwick. 2004. Detecting short directed cycles using rectangular matrix multiplication and dynamic programming.. In SODA, Vol. 4. 254--260.","journal-title":"SODA"},{"key":"e_1_2_1_37_1","first-page":"1","article-title":"Exploiting causal independence in Bayesian network inference","volume":"5","author":"Zhang Nevin Lianwen","year":"1996","unstructured":"Nevin Lianwen Zhang and David Poole. 1996. Exploiting causal independence in Bayesian network inference. J. Artif. Int. Res., Vol. 5, 1 (Dec. 1996), 301--328.","journal-title":"J. Artif. Int. Res."},{"key":"e_1_2_1_38_1","volume-title":"Poole","author":"Zhang Nevin Lianwen","year":"1994","unstructured":"Nevin Lianwen Zhang and David L. Poole. 1994. A simple approach to Bayesian network computations. https:\/\/api.semanticscholar.org\/CorpusID:2978086"}],"container-title":["Proceedings of the ACM on Management of Data"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3725235","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,8,22]],"date-time":"2025-08-22T23:18:28Z","timestamp":1755904708000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3725235"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,9]]},"references-count":38,"journal-issue":{"issue":"2","published-print":{"date-parts":[[2025,6,9]]}},"alternative-id":["10.1145\/3725235"],"URL":"https:\/\/doi.org\/10.1145\/3725235","relation":{},"ISSN":["2836-6573"],"issn-type":[{"value":"2836-6573","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025,6,9]]}}}