{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:40:08Z","timestamp":1747867208014,"version":"3.41.0"},"publisher-location":"Cham","reference-count":23,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783031917356","type":"print"},{"value":"9783031917363","type":"electronic"}],"license":[{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2025,1,1]],"date-time":"2025-01-01T00:00:00Z","timestamp":1735689600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025]]},"DOI":"10.1007\/978-3-031-91736-3_20","type":"book-chapter","created":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:03:24Z","timestamp":1747865004000},"page":"333-349","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Low-Bandwidth Matrix Multiplication: Faster Algorithms and\u00a0More General Forms of\u00a0Sparsity"],"prefix":"10.1007","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0727-160X","authenticated-orcid":false,"given":"Chetan","family":"Gupta","sequence":"first","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0009-0000-5494-1218","authenticated-orcid":false,"given":"Janne H.","family":"Korhonen","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-9887-5192","authenticated-orcid":false,"given":"Jan","family":"Studen\u00fd","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0001-6117-8089","authenticated-orcid":false,"given":"Jukka","family":"Suomela","sequence":"additional","affiliation":[]},{"ORCID":"https:\/\/orcid.org\/0000-0002-0040-1213","authenticated-orcid":false,"given":"Hossein","family":"Vahidi","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2025,5,22]]},"reference":[{"key":"20_CR1","doi-asserted-by":"publisher","unstructured":"Augustine, J., et al.: Distributed computation in node-capacitated networks. In: SPAA 2019, Phoenix, AZ, USA, pp. 69\u201379. ACM (2019). https:\/\/doi.org\/10.1145\/3323165.3323195","DOI":"10.1145\/3323165.3323195"},{"issue":"6","key":"20_CR2","doi-asserted-by":"publisher","first-page":"463","DOI":"10.1007\/S00446-020-00380-5","volume":"34","author":"K Censor-Hillel","year":"2021","unstructured":"Censor-Hillel, K., Dory, M., Korhonen, J.H., Leitersdorf, D.: Fast approximate shortest paths in the congested clique. Distrib. Comput. 34(6), 463\u2013487 (2021). https:\/\/doi.org\/10.1007\/S00446-020-00380-5","journal-title":"Distrib. Comput."},{"issue":"6","key":"20_CR3","doi-asserted-by":"publisher","first-page":"461","DOI":"10.1007\/S00446-016-0270-2","volume":"32","author":"K Censor-Hillel","year":"2019","unstructured":"Censor-Hillel, K., Kaski, P., Korhonen, J.H., Lenzen, C., Paz, A., Suomela, J.: Algebraic methods in the congested clique. Distrib. Comput. 32(6), 461\u2013478 (2019). https:\/\/doi.org\/10.1007\/S00446-016-0270-2","journal-title":"Distrib. Comput."},{"key":"20_CR4","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Le Gall, F., Leitersdorf, D.: On distributed listing of cliques. In: PODC 2020, Italy, pp. 474\u2013482. ACM (2020). https:\/\/doi.org\/10.1145\/3382734.3405742","DOI":"10.1145\/3382734.3405742"},{"key":"20_CR5","doi-asserted-by":"publisher","unstructured":"Censor-Hillel, K., Leitersdorf, D., Turner, E.: Sparse matrix multiplication and triangle listing in the congested clique model. In: OPODIS 2018, Hong Kong, China. LIPIcs, vol.\u00a0125, pp. 4:1\u20134:17 (2018). https:\/\/doi.org\/10.4230\/LIPICS.OPODIS.2018.4","DOI":"10.4230\/LIPICS.OPODIS.2018.4"},{"key":"20_CR6","doi-asserted-by":"publisher","unstructured":"Chang, Y.J., Pettie, S., Saranurak, T., Zhang, H.: Near-optimal distributed triangle enumeration via expander decompositions. J. ACM 68(3), 21:1\u201321:36 (2021). https:\/\/doi.org\/10.1145\/3446330","DOI":"10.1145\/3446330"},{"key":"20_CR7","doi-asserted-by":"publisher","unstructured":"Chang, Y.J., Saranurak, T.: Improved distributed expander decomposition and nearly optimal triangle enumeration. In: Proceedings PODC 2019, Toronto, ON, Canada, pp. 66\u201373. ACM (2019). https:\/\/doi.org\/10.1145\/3293611.3331618","DOI":"10.1145\/3293611.3331618"},{"issue":"1","key":"20_CR8","doi-asserted-by":"publisher","first-page":"87","DOI":"10.1137\/0215006","volume":"15","author":"SA Cook","year":"1986","unstructured":"Cook, S.A., Dwork, C., Reischuk, R.: Upper and lower time bounds for parallel random access machines without simultaneous writes. SIAM J. Comput. 15(1), 87\u201397 (1986). https:\/\/doi.org\/10.1137\/0215006","journal-title":"SIAM J. Comput."},{"issue":"2","key":"20_CR9","doi-asserted-by":"publisher","first-page":"231","DOI":"10.1016\/S0022-0000(05)80003-0","volume":"48","author":"M Dietzfelbinger","year":"1994","unstructured":"Dietzfelbinger, M., Kutylowski, M., Reischuk, R.: Exact lower time bounds for computing Boolean functions on CREW PRAMs. J. Comput. Syst. Sci. 48(2), 231\u2013254 (1994). https:\/\/doi.org\/10.1016\/S0022-0000(05)80003-0","journal-title":"J. Comput. Syst. Sci."},{"key":"20_CR10","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"195","DOI":"10.1007\/978-3-642-33651-5_14","volume-title":"Distributed Computing","author":"D Dolev","year":"2012","unstructured":"Dolev, D., Lenzen, C., Peled, S.: \u201cTri, Tri Again\u2019\u2019: finding triangles and small subgraphs in a distributed setting. In: Aguilera, M.K. (ed.) DISC 2012. LNCS, vol. 7611, pp. 195\u2013209. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33651-5_14"},{"key":"20_CR11","doi-asserted-by":"publisher","unstructured":"Foerster, K.T., Hirvonen, J., Schmid, S., Suomela, J.: On the power of preprocessing in decentralized network optimization. In: IEEE Conference on Computer Communications, INFOCOM 2019, Paris, France, pp. 1450\u20131458. IEEE (2019). https:\/\/doi.org\/10.1109\/INFOCOM.2019.8737382","DOI":"10.1109\/INFOCOM.2019.8737382"},{"key":"20_CR12","doi-asserted-by":"publisher","unstructured":"Foerster, K.T., Korhonen, J.H., Rybicki, J., Schmid, S.: Does preprocessing help under congestion? In: Proceedings PODC 2019, Toronto, ON, Canada, pp. 259\u2013261. ACM (2019). https:\/\/doi.org\/10.1145\/3293611.3331581","DOI":"10.1145\/3293611.3331581"},{"key":"20_CR13","doi-asserted-by":"publisher","unstructured":"Gupta, C., Hirvonen, J., Korhonen, J.H., Studen\u00fd, J., Suomela, J.: Sparse matrix multiplication in the low-bandwidth model. In: SPAA 2022 Philadelphia, PA, USA, pp. 435\u2013444. ACM (2022). https:\/\/doi.org\/10.1145\/3490148.3538575","DOI":"10.1145\/3490148.3538575"},{"key":"20_CR14","doi-asserted-by":"crossref","unstructured":"Gupta, C., Korhonen, J.H., Studen\u00fd, J., Suomela, J., Vahidi, H.: Low-bandwidth matrix multiplication: faster algorithms and more general forms of sparsity (2024). https:\/\/arxiv.org\/abs\/2404.15559","DOI":"10.1145\/3626183.3660270"},{"key":"20_CR15","doi-asserted-by":"publisher","unstructured":"Izumi, T., Le Gall, F.: Triangle finding and listing in CONGEST networks. In: Proceedings of PODC 2017, Washington, DC, USA, pp. 381\u2013389. ACM (2017). https:\/\/doi.org\/10.1145\/3087801.3087811","DOI":"10.1145\/3087801.3087811"},{"key":"20_CR16","doi-asserted-by":"publisher","unstructured":"Korhonen, J.H., Rybicki, J.: Deterministic subgraph detection in broadcast CONGEST. In: OPODIS 2017, Lisbon, Portugal. LIPIcs, vol.\u00a095, pp. 4:1\u20134:16. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik (2017). https:\/\/doi.org\/10.4230\/LIPICS.OPODIS.2017.4","DOI":"10.4230\/LIPICS.OPODIS.2017.4"},{"key":"20_CR17","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/978-3-662-53426-7_5","volume-title":"Distributed Computing","author":"F Le Gall","year":"2016","unstructured":"Le Gall, F.: Further algebraic algorithms in the congested clique model and applications to graph-theoretic problems. In: Gavoille, C., Ilcinkas, D. (eds.) DISC 2016. LNCS, vol. 9888, pp. 57\u201370. Springer, Heidelberg (2016). https:\/\/doi.org\/10.1007\/978-3-662-53426-7_5"},{"key":"20_CR18","doi-asserted-by":"publisher","unstructured":"Lotker, Z., Pavlov, E., Patt-Shamir, B., Peleg, D.: MST construction in o(log log n) communication rounds. In: SPAA 2003, San Diego, California, USA, pp. 94\u2013100. ACM (2003). https:\/\/doi.org\/10.1145\/777412.777428","DOI":"10.1145\/777412.777428"},{"key":"20_CR19","doi-asserted-by":"publisher","unstructured":"Pandurangan, G., Robinson, P., Scquizzato, M.: On the distributed complexity of large-scale graph computations. ACM Trans. Parallel Comput. 8(2), 7:1\u20137:28 (2021). https:\/\/doi.org\/10.1145\/3460900","DOI":"10.1145\/3460900"},{"key":"20_CR20","doi-asserted-by":"publisher","unstructured":"Roughgarden, T., Vassilvitskii, S., Wang, J.R.: Shuffles and circuits (on lower bounds for modern parallel computation). J. ACM 65(6), 41:1\u201341:24 (2018). https:\/\/doi.org\/10.1145\/3232536","DOI":"10.1145\/3232536"},{"key":"20_CR21","doi-asserted-by":"publisher","unstructured":"Schmid, S., Suomela, J.: Exploiting locality in distributed SDN control. In: Proceedings of SIGCOMM HotSDN 2013, pp. 121\u2013126. ACM (2013). https:\/\/doi.org\/10.1145\/2491185.2491198","DOI":"10.1145\/2491185.2491198"},{"issue":"8","key":"20_CR22","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1145\/79173.79181","volume":"33","author":"LG Valiant","year":"1990","unstructured":"Valiant, L.G.: A bridging model for parallel computation. Commun. ACM 33(8), 103\u2013111 (1990). https:\/\/doi.org\/10.1145\/79173.79181","journal-title":"Commun. ACM"},{"key":"20_CR23","doi-asserted-by":"publisher","unstructured":"Williams, V.V., Xu, Y., Xu, Z., Zhou, R.: New bounds for matrix multiplication: from alpha to omega. In: Proceedings of SODA 2024, Alexandria, VA, USA, pp. 3792\u20133835. SIAM (2024). https:\/\/doi.org\/10.1137\/1.9781611977912.134","DOI":"10.1137\/1.9781611977912.134"}],"container-title":["Lecture Notes in Computer Science","Structural Information and Communication Complexity"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-031-91736-3_20","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,21]],"date-time":"2025-05-21T22:03:26Z","timestamp":1747865006000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-031-91736-3_20"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025]]},"ISBN":["9783031917356","9783031917363"],"references-count":23,"URL":"https:\/\/doi.org\/10.1007\/978-3-031-91736-3_20","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2025]]},"assertion":[{"value":"22 May 2025","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"SIROCCO","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Colloquium on Structural Information and Communication Complexity","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Delphi","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Greece","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2025","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2 June 2025","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"4 June 2025","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"32","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sirocco2025","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.torontomu.ca\/sirocco-2025\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}