{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:49:02Z","timestamp":1782971342453,"version":"3.54.5"},"reference-count":67,"publisher":"Association for Computing Machinery (ACM)","issue":"3","license":[{"start":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T00:00:00Z","timestamp":1620864000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"name":"NSF","award":["CCF-1514383, CCF-1637546, and CCF-1815316"],"award-info":[{"award-number":["CCF-1514383, CCF-1637546, and CCF-1815316"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2021,6,30]]},"abstract":"\n We present improved distributed algorithms for variants of the triangle finding problem in the\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n model. We show that triangle detection, counting, and enumeration can be solved in\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds using\n expander decompositions<\/jats:italic>\n . This matches the triangle enumeration lower bound of\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n by Izumi and Le\u00a0Gall [PODC\u201917] and Pandurangan, Robinson, and Scquizzato [SPAA\u201918], which holds even in the\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n model. The previous upper bounds for triangle detection and enumeration in\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n were\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n , respectively, due to Izumi and Le\u00a0Gall [PODC\u201917].\n <\/jats:p>\n \n An\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -expander decomposition of a graph\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n is a clustering of the vertices\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n such that (i) each cluster\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n induces a subgraph with conductance at least\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and (ii) the number of inter-cluster edges is at most\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . We show that an\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -expander decomposition with\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n can be constructed in\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds for any\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n and positive integer\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n . For example, a\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -expander decomposition only requires\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds to compute, which is optimal up to subpolynomial factors, and a\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n -expander decomposition can be computed in\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n rounds, for any arbitrarily small constant\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n .\n <\/jats:p>\n \n Our triangle finding algorithms are based on the following generic framework using expander decompositions, which is of independent interest. We first construct an expander decomposition. For each cluster, we simulate\n \n \n \n \n <\/jats:tex-math>\n <\/jats:alternatives>\n <\/jats:inline-formula>\n algorithms with small overhead by applying the\n expander routing<\/jats:italic>\n algorithm due to Ghaffari, Kuhn, and Su [PODC\u201917] Finally, we deal with inter-cluster edges using recursive calls.\n <\/jats:p>","DOI":"10.1145\/3446330","type":"journal-article","created":{"date-parts":[[2021,5,13]],"date-time":"2021-05-13T20:05:42Z","timestamp":1620936342000},"page":"1-36","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":24,"title":["Near-optimal Distributed Triangle Enumeration via Expander Decompositions"],"prefix":"10.1145","volume":"68","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0109-2432","authenticated-orcid":false,"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"ETH Z\u00fcrich, Switzerland"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Seth","family":"Pettie","sequence":"additional","affiliation":[{"name":"University of Michigan, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Thatchaphol","family":"Saranurak","sequence":"additional","affiliation":[{"name":"Toyota Technological Institute at Chicago, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hengjie","family":"Zhang","sequence":"additional","affiliation":[{"name":"Columbia University, New York, NY, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2021,5,13]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00373-4"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212773"},{"key":"e_1_2_1_3_1","volume-title":"Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918)","author":"Alev Vedat Levi","year":"2018","unstructured":"Vedat Levi Alev , Nima Anari , Lap Chi Lau , and Shayan Oveis Gharan . 2018 . Graph clustering using effective resistance . In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918) . 41:1\u201341:16. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph clustering using effective resistance. In Proceedings of the 9th Innovations in Theoretical Computer Science Conference (ITCS\u201918). 41:1\u201341:16."},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/1502793.1502794"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1002\/rsa.3240050305"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.5555\/3458064.3458235"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405742"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-016-0270-2"},{"key":"e_1_2_1_10_1","volume-title":"Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS\u201918)","volume":"125","author":"Censor-Hillel Keren","year":"2018","unstructured":"Keren Censor-Hillel , Dean Leitersdorf , and Elia Turner . 2018 . Sparse matrix multiplication and triangle listing in the congested clique model . In Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS\u201918) , Vol. 125 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 4:1\u20134:17. Keren Censor-Hillel, Dean Leitersdorf, and Elia Turner. 2018. Sparse matrix multiplication and triangle listing in the congested clique model. In Proceedings of the 22nd International Conference on Principles of Distributed Systems (OPODIS\u201918), Vol. 125. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 4:1\u20134:17."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310486"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331618"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00043"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00042"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055463"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316346"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_2_1_19_1","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC\u201919)","author":"Eden Talya","year":"2019","unstructured":"Talya Eden , Nimrod Fiat , Orr Fischer , Fabian Kuhn , and Rotem Oshman . 2019 . Sublinear-time distributed algorithms for detecting small cliques and eEven cycles . In Proceedings of the International Symposium on Distributed Computing (DISC\u201919) . 15:1\u201315:16. Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. 2019. Sublinear-time distributed algorithms for detecting small cliques and eEven cycles. In Proceedings of the International Symposium on Distributed Computing (DISC\u201919). 15:1\u201315:16."},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441058"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055452"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087823"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933094"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210401"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933109"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/2884435.2884451"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_2_1_28_1","volume-title":"Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918)","volume":"121","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Jason Li . 2018 . New distributed algorithms in almost mixing time via transformations from parallel algorithms . In Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918) , Vol. 121 . Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1\u201331:16. Mohsen Ghaffari and Jason Li. 2018. New distributed algorithms in almost mixing time via transformations from parallel algorithms. In Proceedings of the 32nd International Symposium on Distributed Computing (DISC\u201918), Vol. 121. Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1\u201331:16."},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.24"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.5555\/3381089.3381194"},{"key":"e_1_2_1_31_1","volume-title":"Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS\u201920)","volume":"154","author":"Izumi Taisuke","year":"2020","unstructured":"Taisuke Izumi , Fran\u00e7ois Le Gall , and Fr\u00e9d\u00e9ric Magniez . 2020 . Quantum distributed algorithm for triangle finding in the CONGEST Model . In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS\u201920) , Vol. 154 . Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 23:1\u201323:13. Taisuke Izumi, Fran\u00e7ois Le Gall, and Fr\u00e9d\u00e9ric Magniez. 2020. Quantum distributed algorithm for triangle finding in the CONGEST Model. In Proceedings of the 37th International Symposium on Theoretical Aspects of Computer Science (STACS\u201920), Vol. 154. Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 23:1\u201323:13."},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087811"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175472"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3274663"},{"key":"e_1_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634090"},{"key":"e_1_2_1_38_1","volume-title":"Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918)","author":"Krinninger Sebastian","year":"2018","unstructured":"Sebastian Krinninger and Danupon Nanongkai . 2018 . A faster distributed single-source shortest paths algorithm . In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918) . 686\u2013697. Sebastian Krinninger and Danupon Nanongkai. 2018. A faster distributed single-source shortest paths algorithm. In Proceedings of the 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS\u201918). 686\u2013697."},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1137\/0613066"},{"key":"e_1_2_1_40_1","volume-title":"Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915)","author":"Kuhn Fabian","year":"2015","unstructured":"Fabian Kuhn and Anisur Rahaman Molla . 2015 . Distributed sparse cut approximation . In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915) . 10:1\u201310:14. Fabian Kuhn and Anisur Rahaman Molla. 2015. Distributed sparse cut approximation. In Proceedings of the 19th International Conference on Principles of Distributed Systems (OPODIS\u201915). 10:1\u201310:14."},{"key":"e_1_2_1_41_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1998.0929"},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1007\/BF01303516"},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1109\/FSCS.1990.89553"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/3384772.3385158"},{"key":"e_1_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/2486159.2486180"},{"key":"e_1_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055447"},{"key":"e_1_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_2_1_49_1","unstructured":"Krzysztof Nowicki. 2019. A deterministic algorithm for the MST problem in constant rounds of congested clique. Retrieved from https:\/\/arXiv:1912.04239. Krzysztof Nowicki. 2019. A deterministic algorithm for the MST problem in constant rounds of congested clique. Retrieved from https:\/\/arXiv:1912.04239."},{"key":"e_1_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.5555\/2133036.2133078"},{"key":"e_1_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.5555\/2634074.2634168"},{"key":"e_1_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1145\/3210377.3210409"},{"key":"e_1_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2007.54"},{"key":"e_1_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310597"},{"key":"e_1_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1145\/2684464.2684474"},{"key":"e_1_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(89)90067-9"},{"key":"e_1_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/1374376.1374456"},{"key":"e_1_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007352.1007372"},{"key":"e_1_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1137\/08074489X"},{"key":"e_1_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/080744888"},{"key":"e_1_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/090771430"},{"key":"e_1_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4086\/toc.2008.v004a005"},{"key":"e_1_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055415"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446330","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446330","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3446330","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:47:05Z","timestamp":1750193225000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3446330"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,5,13]]},"references-count":67,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2021,6,30]]}},"alternative-id":["10.1145\/3446330"],"URL":"https:\/\/doi.org\/10.1145\/3446330","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2021,5,13]]},"assertion":[{"value":"2019-11-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2020-12-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2021-05-13","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}