{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,4]],"date-time":"2026-06-04T02:08:32Z","timestamp":1780538912021,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":88,"publisher":"ACM","license":[{"start":{"date-parts":[[2022,7,20]],"date-time":"2022-07-20T00:00:00Z","timestamp":1658275200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"funder":[{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-2008422"],"award-info":[{"award-number":["CCF-2008422"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]},{"name":"NUS ODPRT","award":["R-252-000-C04-133"],"award-info":[{"award-number":["R-252-000-C04-133"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2022,7,20]]},"DOI":"10.1145\/3519270.3538423","type":"proceedings-article","created":{"date-parts":[[2022,7,21]],"date-time":"2022-07-21T16:23:51Z","timestamp":1658420631000},"page":"301-312","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":5,"title":["Narrowing the LOCAL-CONGEST Gaps in Sparse Networks via Expander Decompositions"],"prefix":"10.1145","author":[{"given":"Yi-Jun","family":"Chang","sequence":"first","affiliation":[{"name":"National University of Singapore, Singapore, Singapore"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Hsin-Hao","family":"Su","sequence":"additional","affiliation":[{"name":"Boston College, Chestnut Hill, MA, USA"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2022,7,21]]},"reference":[{"key":"e_1_3_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1137\/17M1112406"},{"key":"e_1_3_2_2_2_1","volume-title":"Proc. 32nd International Symposium on Distributed Computing (DISC). 6:1--6:17","author":"Ahmadi Mohamad","year":"2018","unstructured":"Mohamad Ahmadi , Fabian Kuhn , and Rotem Oshman . 2018 . Distributed Approximate Maximum Matching in the CONGEST Model . In Proc. 32nd International Symposium on Distributed Computing (DISC). 6:1--6:17 . Mohamad Ahmadi, Fabian Kuhn, and Rotem Oshman. 2018. Distributed Approximate Maximum Matching in the CONGEST Model. In Proc. 32nd International Symposium on Distributed Computing (DISC). 6:1--6:17."},{"key":"e_1_3_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933084"},{"key":"e_1_3_2_2_4_1","volume-title":"9th Innovations in Theoretical Computer Science Conference, ITCS 2018","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 9th Innovations in Theoretical Computer Science Conference, ITCS 2018 , January 11 --14 , 2018, Cambridge, MA, USA. 41:1--41:16. Vedat Levi Alev, Nima Anari, Lap Chi Lau, and Shayan Oveis Gharan. 2018. Graph Clustering using Effective Resistance. In 9th Innovations in Theoretical Computer Science Conference, ITCS 2018, January 11--14, 2018, Cambridge, MA, USA. 41:1--41:16."},{"key":"e_1_3_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/3326170"},{"key":"e_1_3_2_2_6_1","volume-title":"Large-Scale Deduplication with Constraints Using Dedupalog. In 2009 IEEE 25th International Conference on Data Engineering. 952--963","author":"Arasu A.","unstructured":"A. Arasu , C. R\u00e9 , and D. Suciu . 2009 . Large-Scale Deduplication with Constraints Using Dedupalog. In 2009 IEEE 25th International Conference on Data Engineering. 952--963 . A. Arasu, C. R\u00e9, and D. Suciu. 2009. Large-Scale Deduplication with Constraints Using Dedupalog. In 2009 IEEE 25th International Conference on Data Engineering. 952--963."},{"key":"e_1_3_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2775105"},{"key":"e_1_3_2_2_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3293611.3331597"},{"key":"e_1_3_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1023\/B:MACH.0000033116.57574.95"},{"key":"e_1_3_2_2_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087806"},{"key":"e_1_3_2_2_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-009-0088-2"},{"key":"e_1_3_2_2_12_1","volume-title":"35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"18","author":"Bonamy Marthe","year":"2021","unstructured":"Marthe Bonamy , Linda Cook , Carla Groenland , and Alexandra Wesolek . 2021 . A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs . In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 13:1--13: 18 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.13 10.4230\/LIPIcs.DISC.2021.13 Marthe Bonamy, Linda Cook, Carla Groenland, and Alexandra Wesolek. 2021. A Tight Local Algorithm for the Minimum Dominating Set Problem in Outerplanar Graphs. In 35th International Symposium on Distributed Computing (DISC 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 209), Seth Gilbert (Ed.). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 13:1--13:18. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2021.13"},{"key":"e_1_3_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2630808"},{"key":"e_1_3_2_2_14_1","volume-title":"Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC)","volume":"209","author":"Cambus M\u00e9lanie","year":"2021","unstructured":"M\u00e9lanie Cambus , Davin Choo , Havu Miikonen , and Jara Uitto . 2021 . Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC) , Vol. 209 . 15:1--15:18. M\u00e9lanie Cambus, Davin Choo, Havu Miikonen, and Jara Uitto. 2021. Massively Parallel Correlation Clustering in Bounded Arboricity Graphs. In 35th International Symposium on Distributed Computing (DISC), Vol. 209. 15:1--15:18."},{"key":"e_1_3_2_2_15_1","volume-title":"48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"14","author":"Censor-Hillel Keren","year":"2021","unstructured":"Keren Censor-Hillel . 2021 . Distributed Subgraph Finding: Progress and Challenges. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 198), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 3:1--3: 14 . https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.3 10.4230\/LIPIcs.ICALP.2021.3 Keren Censor-Hillel. 2021. Distributed Subgraph Finding: Progress and Challenges. In 48th International Colloquium on Automata, Languages, and Programming (ICALP 2021) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 198), Nikhil Bansal, Emanuela Merelli, and James Worrell (Eds.). Schloss Dagstuhl -- Leibniz-Zentrum f\u00fcr Informatik, Dagstuhl, Germany, 3:1--3:14. https:\/\/doi.org\/10.4230\/LIPIcs.ICALP.2021.3"},{"key":"e_1_3_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.171"},{"key":"e_1_3_2_2_17_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-018-0324-8"},{"key":"e_1_3_2_2_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/3382734.3405742"},{"key":"e_1_3_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446330"},{"key":"e_1_3_2_2_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00043"},{"key":"e_1_3_2_2_21_1","volume-title":"Narrowing the LOCAL--CONGEST Gaps in Sparse Networks via Expander Decompositions. arXiv preprint arXiv:2205.08093","author":"Chang Yi-Jun","year":"2022","unstructured":"Yi-Jun Chang and Hsin-Hao Su. 2022. Narrowing the LOCAL--CONGEST Gaps in Sparse Networks via Expander Decompositions. arXiv preprint arXiv:2205.08093 ( 2022 ). Yi-Jun Chang and Hsin-Hao Su. 2022. Narrowing the LOCAL--CONGEST Gaps in Sparse Networks via Expander Decompositions. arXiv preprint arXiv:2205.08093 (2022)."},{"key":"e_1_3_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2004.10.012"},{"key":"e_1_3_2_2_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/2623330.2623743"},{"key":"e_1_3_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS46700.2020.00111"},{"key":"e_1_3_2_2_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/11841036_24"},{"key":"e_1_3_2_2_26_1","volume-title":"Proceedings of the 13th Annual International Conference on Computing and Combinatorics (COCOON). Springer-Verlag","author":"Czygrinow A.","unstructured":"A. Czygrinow and M. Hanckowiak . 2007. Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families . In Proceedings of the 13th Annual International Conference on Computing and Combinatorics (COCOON). Springer-Verlag , Berlin, Heidelberg, 515--525. A. Czygrinow and M. Hanckowiak. 2007. Distributed Approximation Algorithms for Weighted Problems in Minor-Closed Families. In Proceedings of the 13th Annual International Conference on Computing and Combinatorics (COCOON). Springer-Verlag, Berlin, Heidelberg, 515--525."},{"key":"e_1_3_2_2_27_1","volume-title":"Distributed Approximation Algorithms for Planar Graphs. In Italian Conference on Algorithms and Complexity (CIAC).","author":"Czygrinow Andrzej","year":"2006","unstructured":"Andrzej Czygrinow , Michal Hanckowiak , and Edyta Szyma'ska . 2006 . Distributed Approximation Algorithms for Planar Graphs. In Italian Conference on Algorithms and Complexity (CIAC). Andrzej Czygrinow, Michal Hanckowiak, and Edyta Szyma'ska. 2006. Distributed Approximation Algorithms for Planar Graphs. In Italian Conference on Algorithms and Complexity (CIAC)."},{"key":"e_1_3_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-319-14472-6_4"},{"key":"e_1_3_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_3_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.tcs.2019.12.027"},{"key":"e_1_3_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jda.2005.07.006"},{"key":"e_1_3_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/3313276.3316346"},{"key":"e_1_3_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1006\/jagm.1993.1013"},{"key":"e_1_3_2_2_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/2529989"},{"key":"e_1_3_2_2_35_1","volume-title":"Proceedings of the International Symposium on Distributed Computing (DISC). 15:1--15:16","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 Even Cycles . In Proceedings of the International Symposium on Distributed Computing (DISC). 15:1--15:16 . Talya Eden, Nimrod Fiat, Orr Fischer, Fabian Kuhn, and Rotem Oshman. 2019. Sublinear-Time Distributed Algorithms for Detecting Small Cliques and Even Cycles. In Proceedings of the International Symposium on Distributed Computing (DISC). 15:1--15:16."},{"key":"e_1_3_2_2_36_1","doi-asserted-by":"crossref","unstructured":"Yuval Efron Ofer Grossman and Seri Khoury. 2020. Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST. In ACM Symposium on Principles of Distributed Computing (PODC) Yuval Emek and Christian Cachin (Eds.). 511--520.  Yuval Efron Ofer Grossman and Seri Khoury. 2020. Beyond Alice and Bob: Improved Inapproximability for Maximum Independent Set in CONGEST. In ACM Symposium on Principles of Distributed Computing (PODC) Yuval Emek and Christian Cachin (Eds.). 511--520.","DOI":"10.1145\/3382734.3405702"},{"key":"e_1_3_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.5555\/1191547.1191739"},{"key":"e_1_3_2_2_38_1","doi-asserted-by":"publisher","DOI":"10.5555\/1611638.1611641"},{"key":"e_1_3_2_2_39_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-39658-1_21"},{"key":"e_1_3_2_2_40_1","volume-title":"An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor","author":"Fakcharoenphol Jittat","unstructured":"Jittat Fakcharoenphol and Kunal Talwar . 2003. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor . In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, Sanjeev Arora, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Amit Sahai (Eds.). Springer Berlin Heidelberg , Berlin, Heidelberg , 36--46. Jittat Fakcharoenphol and Kunal Talwar. 2003. An Improved Decomposition Theorem for Graphs Excluding a Fixed Minor. In Approximation, Randomization, and Combinatorial Optimization.. Algorithms and Techniques, Sanjeev Arora, Klaus Jansen, Jos\u00e9 D. P. Rolim, and Amit Sahai (Eds.). Springer Berlin Heidelberg, Berlin, Heidelberg, 36--46."},{"key":"e_1_3_2_2_41_1","volume-title":"Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. CoRR abs\/2111.10577","author":"Faour Salwa","year":"2021","unstructured":"Salwa Faour , Marc Fuchs , and Fabian Kuhn . 2021. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. CoRR abs\/2111.10577 ( 2021 ). arXiv:2111.10577 https:\/\/arxiv.org\/abs\/2111.10577 Salwa Faour, Marc Fuchs, and Fabian Kuhn. 2021. Distributed CONGEST Approximation of Weighted Vertex Covers and Matchings. CoRR abs\/2111.10577 (2021). arXiv:2111.10577 https:\/\/arxiv.org\/abs\/2111.10577"},{"key":"e_1_3_2_2_42_1","volume-title":"Improved deterministic distributed matching via rounding. Distributed Computing","author":"Fischer Manuela","year":"2018","unstructured":"Manuela Fischer . 2018. Improved deterministic distributed matching via rounding. Distributed Computing ( 2018 ), 1--13. Manuela Fischer. 2018. Improved deterministic distributed matching via rounding. Distributed Computing (2018), 1--13."},{"key":"e_1_3_2_2_43_1","volume-title":"Deterministic (1+)- Approximate Maximum Matching with poly(1\/) Passes in the Semi-Streaming Model. To appear in STOC 2022 abs\/2106.04179","author":"Fischer Manuela","year":"2021","unstructured":"Manuela Fischer , Slobodan Mitrovic , and Jara Uitto . 2021. Deterministic (1+)- Approximate Maximum Matching with poly(1\/) Passes in the Semi-Streaming Model. To appear in STOC 2022 abs\/2106.04179 ( 2021 ). Manuela Fischer, Slobodan Mitrovic, and Jara Uitto. 2021. Deterministic (1+)- Approximate Maximum Matching with poly(1\/) Passes in the Semi-Streaming Model. To appear in STOC 2022 abs\/2106.04179 (2021)."},{"key":"e_1_3_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611976465.173"},{"key":"e_1_3_2_2_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933109"},{"key":"e_1_3_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611974331.ch16"},{"key":"e_1_3_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/3465084.3467935"},{"key":"e_1_3_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2018.00069"},{"key":"e_1_3_2_2_49_1","volume-title":"Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC). 784--797","author":"Ghaffari M.","unstructured":"M. Ghaffari , F. Kuhn , and Y. Maus . 2017. On the complexity of local distributed graph problems . In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC). 784--797 . https:\/\/doi.org\/10.1145\/3055399.3055471 10.1145\/3055399.3055471 M. Ghaffari, F. Kuhn, and Y. Maus. 2017. On the complexity of local distributed graph problems. In Proceedings of the 49th Annual ACM Symposium on Theory of Computing (STOC). 784--797. https:\/\/doi.org\/10.1145\/3055399.3055471"},{"key":"e_1_3_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/3188745.3188906"},{"key":"e_1_3_2_2_51_1","doi-asserted-by":"publisher","DOI":"10.1145\/3087801.3087827"},{"key":"e_1_3_2_2_52_1","volume-title":"Proceedings 32nd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"16","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 32nd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1--31: 16 . Mohsen Ghaffari and Jason Li. 2018. New Distributed Algorithms in Almost Mixing Time via Transformations from Parallel Algorithms. In Proceedings 32nd International Symposium on Distributed Computing (DISC) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 31:1--31:16."},{"key":"e_1_3_2_2_53_1","volume-title":"31st International Symposium on Distributed Computing (DISC","author":"Ghaffari Mohsen","year":"2017","unstructured":"Mohsen Ghaffari and Merav Parter . 2017 . Near-optimal distributed DFS in planar graphs . In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik. Mohsen Ghaffari and Merav Parter. 2017. Near-optimal distributed DFS in planar graphs. In 31st International Symposium on Distributed Computing (DISC 2017). Schloss Dagstuhl-Leibniz-Zentrum fuer Informatik."},{"key":"e_1_3_2_2_54_1","unstructured":"Apache Giraph. [n.d.]. http:\/\/giraph.apache.org.  Apache Giraph. [n.d.]. http:\/\/giraph.apache.org."},{"key":"e_1_3_2_2_55_1","volume-title":"A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19, 3 (01","author":"Goldreich Oded","year":"1999","unstructured":"Oded Goldreich and Dana Ron . 1999. A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19, 3 (01 Mar 1999 ), 335--373. Oded Goldreich and Dana Ron. 1999. A Sublinear Bipartiteness Tester for Bounded Degree Graphs. Combinatorica 19, 3 (01 Mar 1999), 335--373."},{"key":"e_1_3_2_2_56_1","volume-title":"Proc. 11th USENIX Conference on Operating Systems Design and Implementation (OSDI). 599--613","author":"Gonzalez Joseph E.","year":"2014","unstructured":"Joseph E. Gonzalez , Reynold S. Xin , Ankur Dave , Daniel Crankshaw , Michael J. Franklin , and Ion Stoica . 2014 . GraphX: Graph Processing in a Distributed Dataflow Framework . In Proc. 11th USENIX Conference on Operating Systems Design and Implementation (OSDI). 599--613 . Joseph E. Gonzalez, Reynold S. Xin, Ankur Dave, Daniel Crankshaw, Michael J. Franklin, and Ion Stoica. 2014. GraphX: Graph Processing in a Distributed Dataflow Framework. In Proc. 11th USENIX Conference on Operating Systems Design and Implementation (OSDI). 599--613."},{"key":"e_1_3_2_2_57_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212737"},{"key":"e_1_3_2_2_58_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-662-53426-7_12"},{"key":"e_1_3_2_2_60_1","volume-title":"32nd International Symposium on Distributed Computing (DISC 2018) (Leibniz International Proceedings in Informatics (LIPIcs)","volume":"14","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler and Jason Li . 2018 . Faster Distributed Shortest Path Approximations via Shortcuts . In 32nd International Symposium on Distributed Computing (DISC 2018) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 33:1--33: 14 . https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.33 10.4230\/LIPIcs.DISC.2018.33 Bernhard Haeupler and Jason Li. 2018. Faster Distributed Shortest Path Approximations via Shortcuts. In 32nd International Symposium on Distributed Computing (DISC 2018) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 121), Ulrich Schmid and Josef Widder (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 33:1--33:14. https:\/\/doi.org\/10.4230\/LIPIcs.DISC.2018.33"},{"key":"e_1_3_2_2_61_1","doi-asserted-by":"publisher","DOI":"10.1145\/3212734.3212776"},{"key":"e_1_3_2_2_62_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2019.00048"},{"key":"e_1_3_2_2_63_1","volume-title":"Fran\u00e7ois Le Gall, and Fr\u00e9d\u00e9ric Magniez","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 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (Leibniz International Proceedings in Informatics (LIPIcs) , Vol. 154), Christophe Paul and Markus Bl\u00e4ser (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 23:1--23: 13 . https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.23 10.4230\/LIPIcs.STACS.2020.23 Taisuke Izumi, Fran\u00e7ois Le Gall, and Fr\u00e9d\u00e9ric Magniez. 2020. Quantum Distributed Algorithm for Triangle Finding in the CONGEST Model. In 37th International Symposium on Theoretical Aspects of Computer Science (STACS 2020) (Leibniz International Proceedings in Informatics (LIPIcs), Vol. 154), Christophe Paul and Markus Bl\u00e4ser (Eds.). Schloss Dagstuhl--Leibniz-Zentrum fuer Informatik, Dagstuhl, Germany, 23:1--23:13. https:\/\/doi.org\/10.4230\/LIPIcs.STACS.2020.23"},{"key":"e_1_3_2_2_64_1","doi-asserted-by":"publisher","DOI":"10.1137\/0218077"},{"key":"e_1_3_2_2_65_1","doi-asserted-by":"publisher","DOI":"10.1145\/990308.990313"},{"key":"e_1_3_2_2_66_1","volume-title":"Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC)","volume":"179","author":"Khoury Seri","year":"2020","unstructured":"Ken-ichi Kawarabayashi, Seri Khoury , Aaron Schild , and Gregory Schwartzman . 2020 . Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC) , Vol. 179 . 35:1-- 35:16. Ken-ichi Kawarabayashi, Seri Khoury, Aaron Schild, and Gregory Schwartzman. 2020. Improved Distributed Approximations for Maximum Independent Set. In 34th International Symposium on Distributed Computing (DISC), Vol. 179. 35:1-- 35:16."},{"key":"e_1_3_2_2_67_1","article-title":"Deterministic Edge Connectivity in Near-Linear Time","volume":"66","author":"Kawarabayashi Ken-Ichi","year":"2018","unstructured":"Ken-Ichi Kawarabayashi and Mikkel Thorup . 2018 . Deterministic Edge Connectivity in Near-Linear Time . J. ACM 66 , 1, Article 4 (Dec. 2018), 4:1--4:50 pages. Ken-Ichi Kawarabayashi and Mikkel Thorup. 2018. Deterministic Edge Connectivity in Near-Linear Time. J. ACM 66, 1, Article 4 (Dec. 2018), 4:1--4:50 pages.","journal-title":"J. ACM"},{"key":"e_1_3_2_2_68_1","doi-asserted-by":"publisher","DOI":"10.1145\/167088.167261"},{"key":"e_1_3_2_2_69_1","volume-title":"Proceedings 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 509--520","author":"Kumar A.","unstructured":"A. Kumar , C. Seshadhri , and A. Stolman . 2018. Finding forbidden minors in sublinear time: a O(n1\/2+ O(1))-query one-sided tester for minor closed properties on bounded degree graphs . In Proceedings 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 509--520 . A. Kumar, C. Seshadhri, and A. Stolman. 2018. Finding forbidden minors in sublinear time: a O(n1\/2+ O(1))-query one-sided tester for minor closed properties on bounded degree graphs. In Proceedings 59th Annual IEEE Symposium on Foundations of Computer Science (FOCS). 509--520."},{"key":"e_1_3_2_2_70_1","volume-title":"Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC).","author":"Gall Fran\u00e7ois Le","year":"2021","unstructured":"Fran\u00e7ois Le Gall and Masayuki Miyamoto . 2021 . Lower Bounds for Induced Cycle Detection in Distributed Computing . In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC). Fran\u00e7ois Le Gall and Masayuki Miyamoto. 2021. Lower Bounds for Induced Cycle Detection in Distributed Computing. In Proceedings of the 32nd International Symposium on Algorithms and Computation (ISAAC)."},{"key":"e_1_3_2_2_71_1","volume-title":"Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2","author":"Lenzen Christoph","year":"2013","unstructured":"Christoph Lenzen , Yvonne-Anne Pignolet , and Roger Wattenhofer . 2013. Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2 ( 2013 ), 119--137. Christoph Lenzen, Yvonne-Anne Pignolet, and Roger Wattenhofer. 2013. Distributed minimum dominating set approximations in restricted families of graphs. Distributed computing 26, 2 (2013), 119--137."},{"key":"e_1_3_2_2_72_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-020-00382-3"},{"key":"e_1_3_2_2_73_1","volume-title":"Low diameter graph decompositions. Combinatorica 13, 4 (01","author":"Linial Nathan","year":"1993","unstructured":"Nathan Linial and Michael Saks . 1993. Low diameter graph decompositions. Combinatorica 13, 4 (01 Dec 1993 ), 441--454. Nathan Linial and Michael Saks. 1993. Low diameter graph decompositions. Combinatorica 13, 4 (01 Dec 1993), 441--454."},{"key":"e_1_3_2_2_74_1","doi-asserted-by":"publisher","DOI":"10.1145\/2786753"},{"key":"e_1_3_2_2_75_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807184"},{"key":"e_1_3_2_2_76_1","volume-title":"Article 25 (Oct.","author":"McCune Robert Ryan","year":"2015","unstructured":"Robert Ryan McCune , Tim Weninger , and Greg Madey . 2015. Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing. ACM Comput. Surv. 48, 2 , Article 25 (Oct. 2015 ), 39 pages. Robert Ryan McCune, Tim Weninger, and Greg Madey. 2015. Thinking Like a Vertex: A Survey of Vertex-Centric Frameworks for Large-Scale Distributed Graph Processing. ACM Comput. Surv. 48, 2, Article 25 (Oct. 2015), 39 pages."},{"key":"e_1_3_2_2_77_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(86)90030-9"},{"key":"e_1_3_2_2_78_1","doi-asserted-by":"publisher","DOI":"10.1109\/FOCS.2017.92"},{"key":"e_1_3_2_2_79_1","doi-asserted-by":"publisher","DOI":"10.1145\/1400863.1400880"},{"key":"e_1_3_2_2_80_1","volume-title":"Proc. 28th International Conference on Neural Information Processing Systems (NIPS)","author":"Pan Xinghao","unstructured":"Xinghao Pan , Dimitris Papailiopoulos , Samet Oymak , Benjamin Recht , Kannan Ramchandran , and Michael I. Jordan . 2015. Parallel Correlation Clustering on Big Graphs . In Proc. 28th International Conference on Neural Information Processing Systems (NIPS) ( Montreal, Canada). 82--90. Xinghao Pan, Dimitris Papailiopoulos, Samet Oymak, Benjamin Recht, Kannan Ramchandran, and Michael I. Jordan. 2015. Parallel Correlation Clustering on Big Graphs. In Proc. 28th International Conference on Neural Information Processing Systems (NIPS) (Montreal, Canada). 82--90."},{"key":"e_1_3_2_2_81_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806689.1806792"},{"key":"e_1_3_2_2_82_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jctb.2004.08.001"},{"key":"e_1_3_2_2_83_1","doi-asserted-by":"publisher","DOI":"10.1145\/3357713.3384298"},{"key":"e_1_3_2_2_84_1","volume-title":"Proceedings 36th Annual ACM Symposium on Theory of Computing (STOC). 81--90","author":"Daniel","unstructured":"Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems . In Proceedings 36th Annual ACM Symposium on Theory of Computing (STOC). 81--90 . Daniel A. Spielman and Shang-Hua Teng. 2004. Nearly-linear time algorithms for graph partitioning, graph sparsification, and solving linear systems. In Proceedings 36th Annual ACM Symposium on Theory of Computing (STOC). 81--90."},{"key":"e_1_3_2_2_85_1","volume-title":"Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA)","author":"Swamy Chaitanya","year":"2004","unstructured":"Chaitanya Swamy . 2004 . Correlation Clustering: Maximizing Agreements via Semidefinite Programming . In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) ( New Orleans, Louisiana). 526--527. Chaitanya Swamy. 2004. Correlation Clustering: Maximizing Agreements via Semidefinite Programming. In Proc. 15th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA) (New Orleans, Louisiana). 526--527."},{"key":"e_1_3_2_2_86_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-3975(93)90031-N"},{"key":"e_1_3_2_2_87_1","doi-asserted-by":"publisher","DOI":"10.1006\/jctb.2000.2013"},{"key":"e_1_3_2_2_88_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2013.11.008"}],"event":{"name":"PODC '22: ACM Symposium on Principles of Distributed Computing","location":"Salerno Italy","acronym":"PODC '22","sponsor":["SIGOPS ACM Special Interest Group on Operating Systems","SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 2022 ACM Symposium on Principles of Distributed Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538423","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538423","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3519270.3538423","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,17]],"date-time":"2025-06-17T20:12:20Z","timestamp":1750191140000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3519270.3538423"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2022,7,20]]},"references-count":88,"alternative-id":["10.1145\/3519270.3538423","10.1145\/3519270"],"URL":"https:\/\/doi.org\/10.1145\/3519270.3538423","relation":{},"subject":[],"published":{"date-parts":[[2022,7,20]]},"assertion":[{"value":"2022-07-21","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}