{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,7,2]],"date-time":"2026-07-02T05:35:18Z","timestamp":1782970518065,"version":"3.54.5"},"publisher-location":"New York, NY, USA","reference-count":72,"publisher":"ACM","license":[{"start":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T00:00:00Z","timestamp":1749772800000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2402835"],"award-info":[{"award-number":["CCF-2402835"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733510","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"337-348","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":1,"title":["Sublinear-Time Sampling of Spanning Trees in the Congested Clique"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0002-0834-3476","authenticated-orcid":false,"given":"Sriram V.","family":"Pemmaraju","sequence":"first","affiliation":[{"name":"University of Iowa, Iowa City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0001-9160-1503","authenticated-orcid":false,"given":"Sourya","family":"Roy","sequence":"additional","affiliation":[{"name":"University of Iowa, Iowa City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-7482-0754","authenticated-orcid":false,"given":"Joshua Z.","family":"Sobel","sequence":"additional","affiliation":[{"name":"University of Iowa, Iowa City, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/0403039"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1979.34"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ITCS.2021.83"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451091"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591805"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1287\/opre.2017.1603"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989425"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0895480194264988"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3125644"},{"key":"e_1_3_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1137\/19M1286955"},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1994.365687"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1989.63516"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1988.21964"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2023.11"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.OPODIS.2023.13"},{"key":"e_1_3_2_1_16_1","unstructured":"Keren Censor-Hillel. 2024. Distributed Subgraph Finding: Progress and Challenges. arXiv:2203.06597 [cs.DS] https:\/\/arxiv.org\/abs\/2203.06597"},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767414"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/73007.73062"},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1996.0014"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405751"},{"key":"e_1_3_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/2432622.2432624"},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-33651-5_14"},{"key":"e_1_3_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.comcom.2023.09.028"},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3527213"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_26_1","volume-title":"Rao","author":"Durfee David","year":"2020","unstructured":"David Durfee, John Peebles, Richard Peng, and Anup B. Rao. 2020. Determinant-Preserving Sparsification of SDDM Matrices. SIAM J. Comput. 49 (2020). https:\/\/api.semanticscholar.org\/CorpusID:216387509"},{"key":"e_1_3_2_1_27_1","unstructured":"Weiming Feng Thomas P. Hayes and Yitong Yin. 2018. Distributed Symmetry Breaking in Sampling (Optimal Distributed Randomly Coloring with Fewer Colors). arXiv:1802.06953 [cs.DS] https:\/\/arxiv.org\/abs\/1802.06953"},{"key":"e_1_3_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/3458064.3458191"},{"key":"e_1_3_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087815"},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212757"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.DISC.2018.26"},{"key":"e_1_3_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538436"},{"key":"e_1_3_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1993636.1993647"},{"key":"e_1_3_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087830"},{"key":"e_1_3_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212743"},{"key":"e_1_3_2_1_36_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212750"},{"key":"e_1_3_2_1_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933103"},{"key":"e_1_3_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2011.80"},{"key":"e_1_3_2_1_39_1","unstructured":"Christina Goldschmidt. 2018. Random minimum spanning trees. https:\/\/www.maths.ox.ac.uk\/node\/30217"},{"key":"e_1_3_2_1_40_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-642-25591-5_39"},{"key":"e_1_3_2_1_41_1","volume-title":"Expanders via random spanning trees (SODA '09)","author":"Goyal Navin","unstructured":"Navin Goyal, Luis Rademacher, and Santosh Vempala. 2009. Expanders via random spanning trees (SODA '09). Society for Industrial and Applied Mathematics, USA, 576\u2013585."},{"key":"e_1_3_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1145\/3310131"},{"key":"e_1_3_2_1_43_1","volume-title":"Latin American Symposium on Theoretical Informatics. https:\/\/api.semanticscholar.org\/CorpusID:11554169","author":"Nicholas J.","unstructured":"Nicholas J. A. Harvey and Keyulu Xu. 2016. Generating Random Spanning Trees via Fast Matrix Multiplication. In Latin American Symposium on Theoretical Informatics. https:\/\/api.semanticscholar.org\/CorpusID:11554169"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767434"},{"key":"e_1_3_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-45174-8_35"},{"key":"e_1_3_2_1_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/1008731.1008738"},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(86)90174-X"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.5555\/3174304.3175472"},{"key":"e_1_3_2_1_49_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451009"},{"key":"e_1_3_2_1_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519935.3520062"},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973075.76"},{"key":"e_1_3_2_1_52_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2009.75"},{"key":"e_1_3_2_1_53_1","volume-title":"What Kirchhoff Actually did Concerning Spanning Trees in Electrical Networks and its Relationship to Modern Graph-Theoretical Work. Croatica Chemica Acta 89","author":"Kirby Edward C.","year":"2016","unstructured":"Edward C. Kirby, Roger B. Mallion, Paul Pollak, and Pawel Skrzynski. 2016. What Kirchhoff Actually did Concerning Spanning Trees in Electrical Networks and its Relationship to Modern Graph-Theoretical Work. Croatica Chemica Acta 89 (2016). https:\/\/api.semanticscholar.org\/CorpusID:35908716"},{"key":"e_1_3_2_1_54_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611973730.28"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1145\/2484239.2501983"},{"key":"e_1_3_2_1_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384303"},{"key":"e_1_3_2_1_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/777412.777428"},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","unstructured":"Siqiang Luo. 2019. Distributed PageRank computation: an improved theoretical study. In Proceedings of the Thirty-Third AAAI Conference on Artificial Intelligence and Thirty-First Innovative Applications of Artificial Intelligence Conference and Ninth AAAI Symposium on Educational Advances in Artificial Intelligence (Honolulu Hawaii USA) (AAAI'19\/IAAI'19\/EAAI'19). AAAI Press Article 552 8 pages. 10.1609\/aaai.v33i01.33014496","DOI":"10.1609\/aaai.v33i01.33014496"},{"key":"e_1_3_2_1_60_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ins.2022.05.108"},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"publisher","DOI":"10.1093\/imrn\/rnx082"},{"key":"e_1_3_2_1_62_1","volume-title":"From graphs to matrices, and back: new techniques for graph algorithms. Ph. D. Dissertation","author":"M\u0105dry Aleksander","unstructured":"Aleksander M\u0105dry. 2011. From graphs to matrices, and back: new techniques for graph algorithms. Ph. D. Dissertation. Massachusetts Institute of Technology."},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722263"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"publisher","DOI":"10.1145\/3406325.3451136"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.DISC.2018.40"},{"key":"e_1_3_2_1_66_1","volume-title":"Sobel","author":"Pemmaraju Sriram V.","year":"2024","unstructured":"Sriram V. Pemmaraju, Sourya Roy, and Joshua Z. Sobel. 2024. Sublinear-time Sampling of Spanning Trees in the Congested Clique. arXiv:2411.13334 [cs.DC] https:\/\/arxiv.org\/abs\/2411.13334"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPICS.FSTTCS.2016.47"},{"key":"e_1_3_2_1_68_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-031-32733-9_25"},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188852"},{"key":"e_1_3_2_1_70_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(94)00289-U"},{"key":"e_1_3_2_1_71_1","volume-title":"Foundations and Trends\u00ae in Theoretical Computer Science 7, 1\u20133","author":"Vadhan Salil P","year":"2012","unstructured":"Salil P Vadhan. 2012. Pseudorandomness. Foundations and Trends\u00ae in Theoretical Computer Science 7, 1\u20133 (2012), 1\u2013336."},{"key":"e_1_3_2_1_72_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms. https:\/\/api.semanticscholar.org\/CorpusID:259937341","author":"Williams Virginia Vassilevska","year":"2023","unstructured":"Virginia Vassilevska Williams, Yinzhan Xu, Zixuan Xu, and Renfei Zhou. 2023. New Bounds for Matrix Multiplication: from Alpha to Omega. In ACM-SIAM Symposium on Discrete Algorithms. https:\/\/api.semanticscholar.org\/CorpusID:259937341"},{"key":"e_1_3_2_1_73_1","doi-asserted-by":"publisher","DOI":"10.1145\/237814.237880"}],"event":{"name":"PODC '25: ACM Symposium on Principles of Distributed Computing","location":"Hotel Las Brisas Huatulco Huatulco Mexico","acronym":"PODC '25","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733510","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3732772.3733510","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:25:08Z","timestamp":1749824708000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733510"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":72,"alternative-id":["10.1145\/3732772.3733510","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733510","relation":{},"subject":[],"published":{"date-parts":[[2025,6,13]]},"assertion":[{"value":"2025-06-13","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}