{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:57:38Z","timestamp":1781031458995,"version":"3.54.1"},"publisher-location":"New York, NY, USA","reference-count":70,"publisher":"ACM","license":[{"start":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T00:00:00Z","timestamp":1780963200000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/legalcode"}],"funder":[{"name":"Research Council of Norway","award":["BWCA (314528)"],"award-info":[{"award-number":["BWCA (314528)"]}]},{"name":"Universit\u00e9 Paris Cit\u00e9","award":["METALG"],"award-info":[{"award-number":["METALG"]}]},{"name":"European Research Council","award":["NewPC (101199930)"],"award-info":[{"award-number":["NewPC (101199930)"]}]},{"DOI":"10.13039\/501100001665","name":"Agence Nationale de la Recherche","doi-asserted-by":"publisher","award":["DUCAT (ANR-20-CE48-0006)"],"award-info":[{"award-number":["DUCAT (ANR-20-CE48-0006)"]}],"id":[{"id":"10.13039\/501100001665","id-type":"DOI","asserted-by":"publisher"}]},{"name":"Agence Nationale de la Recherche","award":["PREDICTIONS (ANR-23-CE48-0010)"],"award-info":[{"award-number":["PREDICTIONS (ANR-23-CE48-0010)"]}]},{"name":"Agence Nationale de la Recherche","award":["ENE-DISC (ANR-24-CE48-7768-01)"],"award-info":[{"award-number":["ENE-DISC (ANR-24-CE48-7768-01)"]}]},{"name":"European Commission (Horizon 2020, ERA-NET Cofund QuantERA II)","award":["QOPT (ERA-NET Cofund 2022-25)"],"award-info":[{"award-number":["QOPT (ERA-NET Cofund 2022-25)"]}]},{"name":"Agence Nationale de la Recherche","award":["EPiQ (ANR-22-PETQ-0007)"],"award-info":[{"award-number":["EPiQ (ANR-22-PETQ-0007)"]}]},{"name":"ANID-FONDECYT","award":["1230599"],"award-info":[{"award-number":["1230599"]}]},{"name":"ANID-FONDECYT","award":["1261209"],"award-info":[{"award-number":["1261209"]}]},{"name":"ANID-FONDECYT","award":["FB210005"],"award-info":[{"award-number":["FB210005"]}]},{"name":"ANID-MILENIO","award":["NCN2024_103"],"award-info":[{"award-number":["NCN2024_103"]}]},{"name":"STIC-AmSud","award":["ECODIST (AMSUD240005)"],"award-info":[{"award-number":["ECODIST (AMSUD240005)"]}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2026,6,9]]},"DOI":"10.1145\/3798129.3800849","type":"proceedings-article","created":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T17:53:56Z","timestamp":1781027636000},"page":"1397-1408","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["What Can Be Computed Locally Revisited: First-Order Logic on Sparse Graphs in Distributed Computing"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-0342-9243","authenticated-orcid":false,"given":"L\u00e9lia","family":"Blin","sequence":"first","affiliation":[{"name":"IRIF, Universit\u00e9 Paris Cit\u00e9 and CNRS, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4534-4803","authenticated-orcid":false,"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[{"name":"IRIF, Universit\u00e9 Paris Cit\u00e9 and CNRS, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0009-0004-6308-0500","authenticated-orcid":false,"given":"Sylvain","family":"Gay","sequence":"additional","affiliation":[{"name":"\u00c9cole Normale Sup\u00e9rieure, Paris, France"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2619-2990","authenticated-orcid":false,"given":"Petr A.","family":"Golovach","sequence":"additional","affiliation":[{"name":"University of Bergen, Bergen, Norway"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2508-5907","authenticated-orcid":false,"given":"Pedro","family":"Montealegre","sequence":"additional","affiliation":[{"name":"Universidad Adolfo Ib\u00e1\u00f1ez, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2969-5083","authenticated-orcid":false,"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Santiago, Chile"}],"role":[{"vocabulary":"crossref","role":"author"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-3466-859X","authenticated-orcid":false,"given":"Ioan","family":"Todinca","sequence":"additional","affiliation":[{"name":"Universit\u00e9 d'Orl\u00e9ans, Orl\u00e9ans, France"}],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"320","published-online":{"date-parts":[[2026,6,9]]},"reference":[{"key":"e_1_3_2_1_1_1","article-title":"Distributed Dominating Set Approximations beyond Planar Graphs","volume":"15","author":"Amiri Saeed Akhoondian","year":"2019","unstructured":"Saeed Akhoondian Amiri, Stefan Schmid, and Sebastian Siebertz. 2019. Distributed Dominating Set Approximations beyond Planar Graphs. ACM Transactions on Algorithms, 15, 3 (2019), Article No. 39, 1\u201318.","journal-title":"ACM Transactions on Algorithms"},{"key":"e_1_3_2_1_2_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, 99\u2013109","author":"Baterisna Dan Alden","year":"2025","unstructured":"Dan Alden Baterisna and Yi\u2011Jun Chang. 2025. Optimal Local Certification on Graphs of Bounded Pathwidth. In Proceedings of the 44th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, 99\u2013109."},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933575.2934508"},{"key":"e_1_3_2_1_4_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, 77\u201387","author":"Bonamy Marthe","year":"2025","unstructured":"Marthe Bonamy, Cyril Gavoille, Timoth\u00e9 Picavet, and Alexandra Wesolek. 2025. Local Constant Approximation for Dominating Set on Graphs Excluding Large Minors. In Proceedings of the 44th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, 77\u201387."},{"key":"e_1_3_2_1_5_1","volume-title":"61st IEEE Symposium on Foundations of Computer Science (FOCS). 601\u2013612","author":"Bonnet \u00c9douard","year":"2020","unstructured":"\u00c9douard Bonnet, Eun Jung Kim, St\u00e9phan Thomass\u00e9, and R\u00e9mi Watrigant. 2020. Twin-width I: tractable FO model checking. In 61st IEEE Symposium on Foundations of Computer Science (FOCS). 601\u2013612."},{"key":"e_1_3_2_1_6_1","volume-title":"25th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs","volume":"17","author":"Bousquet Nicolas","year":"2021","unstructured":"Nicolas Bousquet, Laurent Feuilloley, and Th\u00e9o Pierron. 2021. Local Certification of Graph Decompositions and Applications to Minor-Free Classes. In 25th International Conference on Principles of Distributed Systems (OPODIS) (LIPIcs, Vol. 217). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 22:1\u201322:17."},{"key":"e_1_3_2_1_7_1","first-page":"1","article-title":"Distributed Subgraph Finding: Progress and Challenges (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 198)","volume":"3","author":"Censor-Hillel Keren","year":"2021","unstructured":"Keren Censor-Hillel. 2021. Distributed Subgraph Finding: Progress and Challenges (Invited Talk). In 48th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 198). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 3:1\u20133:14.","journal-title":"Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik"},{"key":"e_1_3_2_1_8_1","volume-title":"Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. In 42nd ACM Symposium on Principles of Distributed Computing (PODC). 55\u201366","author":"Chang Yi-Jun","year":"2023","unstructured":"Yi-Jun Chang. 2023. Efficient Distributed Decomposition and Routing Algorithms in Minor-Free Networks and Their Applications. In 42nd ACM Symposium on Principles of Distributed Computing (PODC). 55\u201366."},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/3446330"},{"key":"e_1_3_2_1_10_1","volume-title":"Proceedings of the 44th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, 110\u2013120","author":"Cook Linda","year":"2025","unstructured":"Linda Cook, Eun Jung Kim, and Tom\u00e1s Masar\u00edk. 2025. A Tight Meta\u2011Theorem for LOCAL Certification of MSO_2 Properties within Bounded Treewidth Graphs. In Proceedings of the 44th Annual ACM Symposium on Principles of Distributed Computing (PODC). ACM Press, 110\u2013120."},{"key":"e_1_3_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-87779-0_6"},{"key":"e_1_3_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ISAAC.2018.22"},{"key":"e_1_3_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1137\/11085178X"},{"key":"e_1_3_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.05.004"},{"key":"e_1_3_2_1_17_1","volume-title":"53rd ACM Symposium on Theory of Computing (STOC). 1144\u20131153","author":"Dory Michal","year":"2021","unstructured":"Michal Dory, Yuval Efron, Sagnik Mukhopadhyay, and Danupon Nanongkai. 2021. Distributed weighted min-cut in nearly-optimal time. In 53rd ACM Symposium on Theory of Computing (STOC). 1144\u20131153."},{"key":"e_1_3_2_1_18_1","volume-title":"Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs","volume":"14","author":"Drange P. G.","unstructured":"P. G. Drange, M. S. Dregi, F. V. Fomin, S. Kreutzer, D. Lokshtanov, M. Pilipczuk, M. Pilipczuk, F. Reidl, F. S. Villaamil, S. Saurabh, S. Siebertz, and S. Sikdar. 2016. Kernelization and sparseness: The case of dominating set. In Proceedings of the 33rd International Symposium on Theoretical Aspects of Computer Science (STACS) (LIPIcs, Vol. 47). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 31:1\u201331:14."},{"key":"e_1_3_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_1_21_1","volume-title":"Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs","volume":"14","author":"Eickmeyer K.","unstructured":"K. Eickmeyer, A. C. Giannopoulou, S. Kreutzer, O. Kwon, M. Pilipczuk, R. Rabinovich, and S. Siebertz. 2017. Neighborhood complexity and kernelization for nowhere dense classes of graphs. In Proceedings of the 44th International Colloquium on Automata, Languages, and Programming (ICALP) (LIPIcs, Vol. 80). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 63:1\u201363:14."},{"key":"e_1_3_2_1_22_1","volume-title":"Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"30","author":"Even Guy","year":"2017","unstructured":"Guy Even, Orr Fischer, Pierre Fraigniaud, Tzlil Gonen, Reut Levi, Moti Medina, Pedro Montealegre, Dennis Olivetti, Rotem Oshman, Ivan Rapaport, and Ioan Todinca. 2017. Three Notes on Distributed Property Testing. In 31st International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 91). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 15:1\u201315:30."},{"key":"e_1_3_2_1_23_1","volume-title":"ACM-SIAM Symposium on Discrete Algorithms (SODA). 4409\u20134447","author":"Faour Salwa","year":"2023","unstructured":"Salwa Faour, Mohsen Ghaffari, Christoph Grunau, Fabian Kuhn, and V\u00e1clav Rozhon. 2023. Local Distributed Rounding: Generalized to MIS, Matching, Set Cover, and Beyond. In ACM-SIAM Symposium on Discrete Algorithms (SODA). 4409\u20134447."},{"key":"e_1_3_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538416"},{"key":"e_1_3_2_1_25_1","volume-title":"Survey of Distributed Decision. Bull. EATCS, 119","author":"Feuilloley Laurent","year":"2016","unstructured":"Laurent Feuilloley and Pierre Fraigniaud. 2016. Survey of Distributed Decision. Bull. EATCS, 119 (2016)."},{"key":"e_1_3_2_1_26_1","volume-title":"58th IEEE Symposium on Foundations of Computer Science (FOCS). 180\u2013191","author":"Fischer Manuela","year":"2017","unstructured":"Manuela Fischer, Mohsen Ghaffari, and Fabian Kuhn. 2017. Deterministic Distributed Edge-Coloring via Hypergraph Maximal Matching. In 58th IEEE Symposium on Foundations of Computer Science (FOCS). 180\u2013191."},{"key":"e_1_3_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_3_2_1_28_1","volume-title":"Distributed Model Checking on Graphs of Bounded Treedepth. In 38th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"20","author":"Fomin Fedor V.","year":"2024","unstructured":"Fedor V. Fomin, Pierre Fraigniaud, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. 2024. Distributed Model Checking on Graphs of Bounded Treedepth. In 38th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 319). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 25:1\u201325:20."},{"key":"e_1_3_2_1_29_1","volume-title":"Distributed Certification for Classes of Dense Graphs. In 37th International Symposium on Distributed Computing (DISC) (LIPIcs","volume":"17","author":"Fraigniaud Pierre","year":"2023","unstructured":"Pierre Fraigniaud, Fr\u00e9d\u00e9ric Mazoit, Pedro Montealegre, Ivan Rapaport, and Ioan Todinca. 2023. Distributed Certification for Classes of Dense Graphs. In 37th International Symposium on Distributed Computing (DISC) (LIPIcs, Vol. 281). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 20:1\u201320:17."},{"key":"e_1_3_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00453-023-01185-1"},{"key":"e_1_3_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_1_32_1","volume-title":"Studies in Logic and the Foundations of Mathematics. 107","author":"Gaifman Haim","unstructured":"Haim Gaifman. 1982. On local and non-local properties. In Studies in Logic and the Foundations of Mathematics. 107, Elsevier, 105\u2013135."},{"key":"e_1_3_2_1_33_1","volume-title":"34th IEEE Symposium on the Foundations of Computer Science (FOCS). 659\u2013668","author":"Garay Juan A.","year":"1993","unstructured":"Juan A. Garay, Shay Kutten, and David Peleg. 1993. A sub-linear time distributed algorithm for minimum-weight spanning trees. In 34th IEEE Symposium on the Foundations of Computer Science (FOCS). 659\u2013668."},{"key":"e_1_3_2_1_34_1","volume-title":"Distributed Algorithms for Planar Networks I: Planar Embedding. In 35th ACM Symposium on Principles of Distributed Computing (PODC). 29\u201338","author":"Ghaffari Mohsen","year":"2016","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed Algorithms for Planar Networks I: Planar Embedding. In 35th ACM Symposium on Principles of Distributed Computing (PODC). 29\u201338."},{"key":"e_1_3_2_1_35_1","volume-title":"27th ACM-SIAM Symposium on Discrete Algorithms (SODA). 202\u2013219","author":"Ghaffari Mohsen","year":"2016","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2016. Distributed Algorithms for Planar Networks II: Low-Congestion Shortcuts, MST, and Min-Cut. In 27th ACM-SIAM Symposium on Discrete Algorithms (SODA). 202\u2013219."},{"key":"e_1_3_2_1_36_1","volume-title":"Low-Congestion Shortcuts for Graphs Excluding Dense Minors. In 40th ACM Symposium on Principles of Distributed Computing (PODC). 213\u2013221","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari and Bernhard Haeupler. 2021. Low-Congestion Shortcuts for Graphs Excluding Dense Minors. In 40th ACM Symposium on Principles of Distributed Computing (PODC). 213\u2013221."},{"key":"e_1_3_2_1_37_1","volume-title":"62nd IEEE Symposium on Foundations of Computer Science (FOCS). 1009\u20131020","author":"Ghaffari Mohsen","year":"2021","unstructured":"Mohsen Ghaffari and Fabian Kuhn. 2021. Deterministic Distributed Vertex Coloring: Simpler, Faster, and without Network Decomposition. In 62nd IEEE Symposium on Foundations of Computer Science (FOCS). 1009\u20131020."},{"key":"e_1_3_2_1_38_1","volume-title":"31st International Symposium on Distributed Computing (DISC). 21:1\u201321:16","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). 21:1\u201321:16."},{"key":"e_1_3_2_1_39_1","volume-title":"Thilikos","author":"Golovach Petr A.","year":"2023","unstructured":"Petr A. Golovach, Giannos Stamoulis, and Dimitrios M. Thilikos. 2023. Model-Checking for First-Order Logic with Disjoint Paths Predicates in Proper Minor-Closed Graph Classes. In Proceedings of the 2023 Annual ACM-SIAM Symposium on Discrete Algorithms (SODA). SIAM, 3684\u20133699."},{"key":"e_1_3_2_1_40_1","first-page":"1","article-title":"Locally Checkable Proofs in Distributed Computing","volume":"12","author":"G\u00f6\u00f6s Mika","year":"2016","unstructured":"Mika G\u00f6\u00f6s and Jukka Suomela. 2016. Locally Checkable Proofs in Distributed Computing. Theory Comput., 12, 1 (2016), 1\u201333.","journal-title":"Theory Comput."},{"key":"e_1_3_2_1_41_1","volume-title":"Honor of Wolfgang Thomas (Texts in Logic and Games","volume":"422","author":"Grohe Martin","year":"2008","unstructured":"Martin Grohe. 2008. Logic, graphs, and algorithms. In Logic and Automata: History and Perspectives, in Honor of Wolfgang Thomas (Texts in Logic and Games, Vol. 2). Amsterdam University Press, 357\u2013422."},{"key":"e_1_3_2_1_42_1","first-page":"181","article-title":"Methods for Algorithmic Meta Theorems","author":"Grohe Martin","year":"2009","unstructured":"Martin Grohe and Stephan Kreutzer. 2009. Methods for Algorithmic Meta Theorems. In Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session. 558, AMS, 181\u2013206.","journal-title":"Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session. 558, AMS"},{"key":"e_1_3_2_1_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591851"},{"key":"e_1_3_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/2933057.2933112"},{"key":"e_1_3_2_1_45_1","volume-title":"Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs. In 30th International Symposium on Distributed Computing (DISC) (LNCS","volume":"172","author":"Haeupler Bernhard","year":"2016","unstructured":"Bernhard Haeupler, Taisuke Izumi, and Goran Zuzic. 2016. Near-Optimal Low-Congestion Shortcuts on Bounded Parameter Graphs. In 30th International Symposium on Distributed Computing (DISC) (LNCS, Vol. 9888). Springer, 158\u2013172."},{"key":"e_1_3_2_1_46_1","volume-title":"Minor Excluded Network Families Admit Fast Distributed Algorithms. In ACM Symposium on Principles of Distributed Computing (PODC). ACM, 465\u2013474","author":"Haeupler Bernhard","year":"2018","unstructured":"Bernhard Haeupler, Jason Li, and Goran Zuzic. 2018. Minor Excluded Network Families Admit Fast Distributed Algorithms. In ACM Symposium on Principles of Distributed Computing (PODC). ACM, 465\u2013474."},{"key":"e_1_3_2_1_47_1","doi-asserted-by":"publisher","DOI":"10.1137\/16M1079336"},{"key":"e_1_3_2_1_48_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2023.103773"},{"key":"e_1_3_2_1_49_1","volume-title":"34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 11\u201322","author":"Izumi Taisuke","year":"2022","unstructured":"Taisuke Izumi, Naoki Kitamura, Takamasa Naruse, and Gregory Schwartzman. 2022. Fully polynomial-time distributed computation in low-treewidth graphs. In 34th ACM Symposium on Parallelism in Algorithms and Architectures (SPAA). ACM, 11\u201322."},{"key":"e_1_3_2_1_50_1","volume-title":"Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017)","volume":"16","author":"Janne","unstructured":"Janne H. Korhonen and Joel Rybicki. 2018. Deterministic Subgraph Detection in Broadcast CONGEST. In 21st International Conference on Principles of Distributed Systems (OPODIS 2017) (LIPIcs, Vol. 95). Schloss Dagstuhl\u2013Leibniz-Zentrum fuer Informatik, 4:1\u20134:16."},{"key":"e_1_3_2_1_51_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_2_1_52_1","series-title":"Mathematical Society Lecture Note Series","volume-title":"Algorithmic meta-theorems","author":"Kreutzer Stephan","unstructured":"Stephan Kreutzer. 2011. Algorithmic meta-theorems. In Finite and Algorithmic Model Theory, Javier Esparza, Christian Michaux, and Charles Steinhorn (Eds.) (London Mathematical Society Lecture Note Series, Vol. 379). Cambridge University Press, 177\u2013270."},{"key":"e_1_3_2_1_53_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-79527-6_19"},{"key":"e_1_3_2_1_54_1","volume-title":"ACM Symposium on Theory of Computing Conference (STOC). 381\u2013390","author":"Lenzen Christoph","year":"2013","unstructured":"Christoph Lenzen and Boaz Patt-Shamir. 2013. Fast routing table construction using small messages. In ACM Symposium on Theory of Computing Conference (STOC). 381\u2013390."},{"key":"e_1_3_2_1_55_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-013-0186-z"},{"key":"e_1_3_2_1_56_1","doi-asserted-by":"publisher","DOI":"10.1137\/0221015"},{"key":"e_1_3_2_1_57_1","volume-title":"Computing Minimum Weight Cycle in the CONGEST Model. In 43rd ACM Symposium on Principles of Distributed Computing (PODC). 182\u2013193","author":"Manoharan Vignesh","year":"2024","unstructured":"Vignesh Manoharan and Vijaya Ramachandran. 2024. Computing Minimum Weight Cycle in the CONGEST Model. In 43rd ACM Symposium on Principles of Distributed Computing (PODC). 182\u2013193."},{"key":"e_1_3_2_1_58_1","volume-title":"ACM Symposium on Theory of Computing (STOC). 565\u2013573","author":"Nanongkai Danupon","year":"2014","unstructured":"Danupon Nanongkai. 2014. Distributed approximation algorithms for weighted shortest paths. In ACM Symposium on Theory of Computing (STOC). 565\u2013573."},{"key":"e_1_3_2_1_59_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539793254571"},{"key":"e_1_3_2_1_60_1","volume-title":"38th Annual ACM Symposium on Theory of Computing (STOC). 391\u2013400","author":"Ne\u0161et\u0159il Jaroslav","year":"2006","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2006. Linear time low tree-width partitions and algorithmic consequences. In 38th Annual ACM Symposium on Theory of Computing (STOC). 391\u2013400."},{"key":"e_1_3_2_1_61_1","doi-asserted-by":"crossref","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity \u2013 Graphs Structures and Algorithms (Algorithms and combinatorics Vol. 28). Springer.","DOI":"10.1007\/978-3-642-27875-4"},{"key":"e_1_3_2_1_62_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0251-x"},{"key":"e_1_3_2_1_63_1","doi-asserted-by":"publisher","DOI":"10.1007\/PL00008932"},{"key":"e_1_3_2_1_64_1","doi-asserted-by":"crossref","unstructured":"David Peleg. 2000. Distributed computing: a locality-sensitive approach. SIAM.","DOI":"10.1137\/1.9780898719772"},{"key":"e_1_3_2_1_65_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539700369740"},{"key":"e_1_3_2_1_66_1","doi-asserted-by":"publisher","DOI":"10.4230\/LIPIcs.ICALP.2022.102"},{"key":"e_1_3_2_1_67_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209136"},{"key":"e_1_3_2_1_68_1","volume-title":"Proceedings of the 30th EACSL Annual Conference on Computer Science Logic (CSL) (LIPIcs","volume":"17","author":"Schirrmacher Nicole","year":"2022","unstructured":"Nicole Schirrmacher, Sebastian Siebertz, and Alexandre Vigny. 2022. First-Order Logic with Connectivity Operators. In Proceedings of the 30th EACSL Annual Conference on Computer Science Logic (CSL) (LIPIcs, Vol. 216). Schloss Dagstuhl\u2013Leibniz-Zentrum f\u00fcr Informatik, 34:1\u201334:17."},{"key":"e_1_3_2_1_69_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"},{"key":"e_1_3_2_1_70_1","volume-title":"Parameterized Distributed Complexity Theory: A logical approach. CoRR, abs\/1903.00505","author":"Siebertz Sebastian","year":"2019","unstructured":"Sebastian Siebertz and Alexandre Vigny. 2019. Parameterized Distributed Complexity Theory: A logical approach. CoRR, abs\/1903.00505 (2019), arXiv:1903.00505."}],"event":{"name":"STOC '26: 58th Annual ACM Symposium on Theory of Computing","location":"Salt Lake City UT USA","acronym":"STOC '26","sponsor":["SIGACT ACM Special Interest Group on Algorithms and Computation Theory"]},"container-title":["Proceedings of the 58th Annual ACM Symposium on Theory of Computing"],"original-title":[],"link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3798129.3800849","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,9]],"date-time":"2026-06-09T18:05:49Z","timestamp":1781028349000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3798129.3800849"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026,6,9]]},"references-count":70,"alternative-id":["10.1145\/3798129.3800849","10.1145\/3798129"],"URL":"https:\/\/doi.org\/10.1145\/3798129.3800849","relation":{},"subject":[],"published":{"date-parts":[[2026,6,9]]},"assertion":[{"value":"2026-06-09","order":3,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}