{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:19:42Z","timestamp":1750220382725,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":39,"publisher":"ACM","license":[{"start":{"date-parts":[[2021,7,21]],"date-time":"2021-07-21T00:00:00Z","timestamp":1626825600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100007567","name":"City University of Hong Kong","doi-asserted-by":"publisher","award":["Project No. 7200639\/CS"],"award-info":[{"award-number":["Project No. 7200639\/CS"]}],"id":[{"id":"10.13039\/100007567","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NSF","award":["IIS-1633720, CCF-1717075,CCF-1540512,IIS-1955939"],"award-info":[{"award-number":["IIS-1633720, CCF-1717075,CCF-1540512,IIS-1955939"]}]},{"name":"BSF","award":["2016419"],"award-info":[{"award-number":["2016419"]}]},{"name":"Research Grants Council (HKSAR)","award":["Project No. CityU 11213620"],"award-info":[{"award-number":["Project No. CityU 11213620"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2021,7,21]]},"DOI":"10.1145\/3465084.3467909","type":"proceedings-article","created":{"date-parts":[[2021,7,23]],"date-time":"2021-07-23T21:09:28Z","timestamp":1627074568000},"page":"247-257","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Can We Break Symmetry with o(m) Communication?"],"prefix":"10.1145","author":[{"given":"Shreyas","family":"Pai","sequence":"first","affiliation":[{"name":"University of Iowa, Iowa City, IA, USA"}]},{"given":"Gopal","family":"Pandurangan","sequence":"additional","affiliation":[{"name":"University of Houston, Houston, TX, USA"}]},{"given":"Sriram V.","family":"Pemmaraju","sequence":"additional","affiliation":[{"name":"University of Iowa, Iowa City, IA, USA"}]},{"given":"Peter","family":"Robinson","sequence":"additional","affiliation":[{"name":"City University of Hong Kong, Kowloon Tong, Hong Kong"}]}],"member":"320","published-online":{"date-parts":[[2021,7,23]]},"reference":[{"key":"e_1_3_2_2_1_1","volume-title":"A Tradeoff between Information and Communication in Broadcast Protocols. 319 LNCS, 2","author":"Awerbuch Baruch","year":"1988","unstructured":"Baruch Awerbuch , Oded Goldreich , David Peleg , and Ronen Vainish . 1988. A Tradeoff between Information and Communication in Broadcast Protocols. 319 LNCS, 2 ( 1988 ), 369--379. https:\/\/doi.org\/10.1007\/BFb0040404 Baruch Awerbuch, Oded Goldreich, David Peleg, and Ronen Vainish. 1988. A Tradeoff between Information and Communication in Broadcast Protocols. 319 LNCS, 2 (1988), 369--379. https:\/\/doi.org\/10.1007\/BFb0040404"},{"volume-title":"Distributed Graph Coloring: Fundamentals and Recent Developments","author":"Barenboim Leonid","key":"e_1_3_2_2_2_1","unstructured":"Leonid Barenboim and Michael Elkin . 2013. Distributed Graph Coloring: Fundamentals and Recent Developments . Morgan & Claypool Publishers . Leonid Barenboim and Michael Elkin. 2013. Distributed Graph Coloring: Fundamentals and Recent Developments. Morgan & Claypool Publishers."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2012.60"},{"key":"e_1_3_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188964"},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331607"},{"key":"e_1_3_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/12130.12151"},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405751"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3380546"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch20"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.5555\/3310435.3310485"},{"key":"e_1_3_2_2_11_1","volume-title":"32nd International Symposium on Distributed Computing, DISC 2018","author":"Ghaffari Mohsen","year":"2018","unstructured":"Mohsen Ghaffari and Fabian Kuhn . 2018 . Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping . In 32nd International Symposium on Distributed Computing, DISC 2018 , New Orleans, LA, USA, October 15--19 , 2018 (LIPIcs), Ulrich Schmid and Josef Widder (Eds.), Vol. 121. 30:1--30:12. Mohsen Ghaffari and Fabian Kuhn. 2018. Distributed MST and Broadcast with Fewer Messages, and Faster Gossiping. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15--19, 2018 (LIPIcs), Ulrich Schmid and Josef Widder (Eds.), Vol. 121. 30:1--30:12."},{"key":"e_1_3_2_2_12_1","volume-title":"Time-Message Trade-Offs in Distributed Algorithms. In 32nd International Symposium on Distributed Computing, DISC 2018","author":"Gmyr Robert","year":"2018","unstructured":"Robert Gmyr and Gopal Pandurangan . 2018 . Time-Message Trade-Offs in Distributed Algorithms. In 32nd International Symposium on Distributed Computing, DISC 2018 , New Orleans, LA, USA, October 15--19 , 2018 (LIPIcs), Ulrich Schmid and Josef Widder (Eds.), Vol. 121. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1--32:18. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.32 Robert Gmyr and Gopal Pandurangan. 2018. Time-Message Trade-Offs in Distributed Algorithms. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15--19, 2018 (LIPIcs), Ulrich Schmid and Josef Widder (Eds.), Vol. 121. Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 32:1--32:18. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.32"},{"key":"e_1_3_2_2_13_1","volume-title":"Efficient Randomized Distributed Coloring in CONGEST. CoRR abs\/2012.14169","author":"Halld\u00f3rsson Magn\u00fas M.","year":"2020","unstructured":"Magn\u00fas M. Halld\u00f3rsson , Fabian Kuhn , Yannic Maus , and Tigran Tonoyan . 2020. Efficient Randomized Distributed Coloring in CONGEST. CoRR abs\/2012.14169 ( 2020 ). https:\/\/arxiv.org\/abs\/2012.14169 Magn\u00fas M. Halld\u00f3rsson, Fabian Kuhn, Yannic Maus, and Tigran Tonoyan. 2020. Efficient Randomized Distributed Coloring in CONGEST. CoRR abs\/2012.14169 (2020). https:\/\/arxiv.org\/abs\/2012.14169"},{"key":"e_1_3_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.5555\/1873601.1873677"},{"key":"e_1_3_2_2_15_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.312.0249"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/2767386.2767405"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.5555\/2722129.2722157"},{"key":"e_1_3_2_2_18_1","volume-title":"MIS in the Congested Clique Model in O(log log ?) Rounds. CoRR abs\/1802.07647","author":"Konrad Christian","year":"2018","unstructured":"Christian Konrad . 2018. MIS in the Congested Clique Model in O(log log ?) Rounds. CoRR abs\/1802.07647 ( 2018 ). arXiv:1802.07647 http:\/\/arxiv.org\/abs\/1802. 07647 Christian Konrad. 2018. MIS in the Congested Clique Model in O(log log ?) Rounds. CoRR abs\/1802.07647 (2018). arXiv:1802.07647 http:\/\/arxiv.org\/abs\/1802. 07647"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1137\/0216019"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2699440"},{"key":"e_1_3_2_2_21_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539704441848"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/22145.22146"},{"key":"e_1_3_2_2_24_1","volume-title":"32nd International Symposium on Distributed Computing, DISC 2018","volume":"121","author":"Mashreghi Ali","year":"2018","unstructured":"Ali Mashreghi and Valerie King . 2018 . Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model . In 32nd International Symposium on Distributed Computing, DISC 2018 , New Orleans, LA, USA, October 15--19 , 2018 (LIPIcs), Vol. 121 . 37:1--37:17. Ali Mashreghi and Valerie King. 2018. Broadcast and Minimum Spanning Tree with o(m) Messages in the Asynchronous CONGEST Model. In 32nd International Symposium on Distributed Computing, DISC 2018, New Orleans, LA, USA, October 15--19, 2018 (LIPIcs), Vol. 121. 37:1--37:17."},{"key":"e_1_3_2_2_25_1","volume-title":"Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. In 33rd International Symposium on Distributed Computing, DISC 2019","author":"Mashreghi Ali","year":"2019","unstructured":"Ali Mashreghi and Valerie King . 2019 . Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. In 33rd International Symposium on Distributed Computing, DISC 2019 , October 14 --18 , 2019, Budapest, Hungary (LIPIcs), Jukka Suomela (Ed.), Vol. 146. 49:1--49:3. Ali Mashreghi and Valerie King. 2019. Brief Announcement: Faster Asynchronous MST and Low Diameter Tree Construction with Sublinear Communication. In 33rd International Symposium on Distributed Computing, DISC 2019, October 14--18, 2019, Budapest, Hungary (LIPIcs), Jukka Suomela (Ed.), Vol. 146. 49:1--49:3."},{"volume-title":"Randomized Algorithms","author":"Motwani Rajeev","key":"e_1_3_2_2_26_1","unstructured":"Rajeev Motwani and Prabhakar Raghavan . 1995. Randomized Algorithms . Cambridge University Press , USA. Rajeev Motwani and Prabhakar Raghavan. 1995. Randomized Algorithms. Cambridge University Press, USA."},{"key":"e_1_3_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/0404036"},{"key":"e_1_3_2_2_28_1","volume-title":"Symmetry Breaking in the Congest Model: Time-and MessageEfficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing, DISC 2017","volume":"91","author":"Pai Shreyas","year":"2017","unstructured":"Shreyas Pai , Gopal Pandurangan , Sriram V. Pemmaraju , Talal Riaz , and Peter Robinson . 2017 . Symmetry Breaking in the Congest Model: Time-and MessageEfficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing, DISC 2017 , October 16 --20 , 2017, Vienna, Austria (LIPIcs), Vol. 91 . 38:1--38:16. Shreyas Pai, Gopal Pandurangan, Sriram V. Pemmaraju, Talal Riaz, and Peter Robinson. 2017. Symmetry Breaking in the Congest Model: Time-and MessageEfficient Algorithms for Ruling Sets. In 31st International Symposium on Distributed Computing, DISC 2017, October 16--20, 2017, Vienna, Austria (LIPIcs), Vol. 91. 38:1--38:16."},{"key":"e_1_3_2_2_29_1","unstructured":"Shreyas Pai Gopal Pandurangan Sriram V. Pemmaraju and Peter Robinson. 2021. Can We Break Symmetry with o(m) Communication? arXiv:cs.DC\/2105.08917  Shreyas Pai Gopal Pandurangan Sriram V. Pemmaraju and Peter Robinson. 2021. Can We Break Symmetry with o(m) Communication? arXiv:cs.DC\/2105.08917"},{"key":"e_1_3_2_2_30_1","volume-title":"Pemmaraju","author":"Pai Shreyas","year":"2020","unstructured":"Shreyas Pai and Sriram V . Pemmaraju . 2020 . Connectivity Lower Bounds in Broadcast Congested Clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs)), Nitin Saxena and Sunil Simon (Eds.), Vol. 182 . Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany , 32:1--32:17. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2020.32 Shreyas Pai and Sriram V. Pemmaraju. 2020. Connectivity Lower Bounds in Broadcast Congested Clique. In 40th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2020) (Leibniz International Proceedings in Informatics (LIPIcs)), Nitin Saxena and Sunil Simon (Eds.), Vol. 182. Schloss Dagstuhl--Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 32:1--32:17. https:\/\/doi.org\/10.4230\/LIPIcs.FSTTCS.2020.32"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/3055399.3055449"},{"key":"e_1_3_2_2_32_1","volume-title":"SSS 2017, Boston, MA, USA, November 5--8, 2017, Proceedings (Lecture Notes in Computer Science), Paul G. Spirakis and Philippas Tsigas (Eds.)","volume":"10616","author":"Patt-Shamir Boaz","year":"2017","unstructured":"Boaz Patt-Shamir and Mor Perry . 2017 . Proof-Labeling Schemes: Broadcast, Unicast and in Between. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium , SSS 2017, Boston, MA, USA, November 5--8, 2017, Proceedings (Lecture Notes in Computer Science), Paul G. Spirakis and Philippas Tsigas (Eds.) , Vol. 10616 . Springer, 1--17. https:\/\/doi.org\/10.1007\/978--3--319--69084- 1_1 Boaz Patt-Shamir and Mor Perry. 2017. Proof-Labeling Schemes: Broadcast, Unicast and in Between. In Stabilization, Safety, and Security of Distributed Systems - 19th International Symposium, SSS 2017, Boston, MA, USA, November 5--8, 2017, Proceedings (Lecture Notes in Computer Science), Paul G. Spirakis and Philippas Tsigas (Eds.), Vol. 10616. Springer, 1--17. https:\/\/doi.org\/10.1007\/978--3--319--69084- 1_1"},{"key":"e_1_3_2_2_33_1","volume-title":"Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners. In ACM-SIAM Symposium on Discrete Algorithms (SODA).","author":"Robinson Peter","year":"2021","unstructured":"Peter Robinson . 2021 . Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners. In ACM-SIAM Symposium on Discrete Algorithms (SODA). Peter Robinson. 2021. Being Fast Means Being Chatty: The Local Information Cost of Graph Spanners. In ACM-SIAM Symposium on Discrete Algorithms (SODA)."},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405721"},{"key":"e_1_3_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"volume-title":"Chernoff-Hoeffding Bounds for Applications with Limited Independence","author":"Schmidt Jeanette P.","key":"e_1_3_2_2_36_1","unstructured":"Jeanette P. Schmidt , Alan Siegel , and Aravind Srinivasan . 1993. Chernoff-Hoeffding Bounds for Applications with Limited Independence . Society for Industrial and Applied Mathematics , USA , 331--340. Jeanette P. Schmidt, Alan Siegel, and Aravind Srinivasan. 1993. Chernoff-Hoeffding Bounds for Applications with Limited Independence. Society for Industrial and Applied Mathematics, USA, 331--340."},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000010"},{"key":"e_1_3_2_2_38_1","volume-title":"Proceedings of the 18th Annual Symposium on Foundations of Computer Science (SFCS '77)","author":"Chi-Chin Yao Andrew","year":"1977","unstructured":"Andrew Chi-Chin Yao . 1977 . Probabilistic Computations: Toward a Unified Measure of Complexity . In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (SFCS '77) . IEEE Computer Society, USA, 222--227. https:\/\/doi.org\/10.1109\/SFCS. 1977.2 Andrew Chi-Chin Yao. 1977. Probabilistic Computations: Toward a Unified Measure of Complexity. In Proceedings of the 18th Annual Symposium on Foundations of Computer Science (SFCS '77). IEEE Computer Society, USA, 222--227. https:\/\/doi.org\/10.1109\/SFCS.1977.2"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"crossref","unstructured":"\u00d6jvind Johansson. 1999. Simple Distributed ( + 1)-Coloring of Graphs. Information Processing Letters 70 70  \u00d6jvind Johansson. 1999. Simple Distributed ( + 1)-Coloring of Graphs. Information Processing Letters 70 70","DOI":"10.1016\/S0020-0190(99)00064-2"}],"event":{"name":"PODC '21: ACM Symposium on Principles of Distributed Computing","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"],"location":"Virtual Event Italy","acronym":"PODC '21"},"container-title":["Proceedings of the 2021 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467909","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467909","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3465084.3467909","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:18:25Z","timestamp":1750191505000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3465084.3467909"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2021,7,21]]},"references-count":39,"alternative-id":["10.1145\/3465084.3467909","10.1145\/3465084"],"URL":"https:\/\/doi.org\/10.1145\/3465084.3467909","relation":{},"subject":[],"published":{"date-parts":[[2021,7,21]]},"assertion":[{"value":"2021-07-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}