{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,14]],"date-time":"2025-06-14T04:06:25Z","timestamp":1749873985256,"version":"3.41.0"},"publisher-location":"New York, NY, USA","reference-count":25,"publisher":"ACM","content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":[],"published-print":{"date-parts":[[2025,6,16]]},"DOI":"10.1145\/3732772.3733507","type":"proceedings-article","created":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:23:34Z","timestamp":1749824614000},"page":"310-313","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":0,"title":["Brief Announcement: Deciding FO Formulas Efficiently in Congested Networks"],"prefix":"10.1145","author":[{"ORCID":"https:\/\/orcid.org\/0000-0003-1955-4612","authenticated-orcid":false,"given":"Fedor V.","family":"Fomin","sequence":"first","affiliation":[{"name":"University of Bergen, Bergen, Norway"}]},{"ORCID":"https:\/\/orcid.org\/0000-0003-4534-4803","authenticated-orcid":false,"given":"Pierre","family":"Fraigniaud","sequence":"additional","affiliation":[{"name":"Universit\u00e9 Paris Cit\u00e9 and CNRS, Paris, France"}]},{"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"}]},{"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"}]},{"ORCID":"https:\/\/orcid.org\/0000-0002-2969-5083","authenticated-orcid":false,"given":"Ivan","family":"Rapaport","sequence":"additional","affiliation":[{"name":"Universidad de Chile, Santiago, Chile"}]},{"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"}]}],"member":"320","published-online":{"date-parts":[[2025,6,13]]},"reference":[{"key":"e_1_3_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-014-0221-8"},{"key":"e_1_3_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1137\/1.9781611975482.51"},{"key":"e_1_3_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/0890-5401(90)90043-H"},{"key":"e_1_3_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/LICS.2007.31"},{"key":"e_1_3_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.jcss.2019.05.004"},{"key":"e_1_3_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/2611462.2611493"},{"key":"e_1_3_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499483"},{"key":"e_1_3_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/3519270.3538416"},{"key":"e_1_3_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539799360768"},{"key":"e_1_3_2_1_10_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_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2499228"},{"key":"e_1_3_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/504794.504798"},{"key":"e_1_3_2_1_13_1","volume-title":"Lower Bounds for Induced Cycle Detection in Distributed Computing. In 32nd International Symposium on Algorithms and Computation (ISAAC) (LIPIcs","volume":"19","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 32nd International Symposium on Algorithms and Computation (ISAAC) (LIPIcs, Vol. 212). Schloss Dagstuhl - Leibniz-Zentrum f\u00fcr Informatik, 58:1\u201358:19."},{"key":"e_1_3_2_1_14_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_15_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_16_1","volume-title":"Model Theoretic Methods in Finite Combinatorics - AMS-ASL Joint Special Session","volume":"558","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, Vol. 558. AMS, 181\u2013206."},{"key":"e_1_3_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/2591796.2591851"},{"key":"e_1_3_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-010-0095-3"},{"key":"e_1_3_2_1_19_1","volume-title":"Finite and Algorithmic Model Theory","author":"Kreutzer Stephan","unstructured":"Stephan Kreutzer. 2011. Algorithmic meta-theorems. In Finite and Algorithmic Model Theory. London Mathematical Society Lecture Note Series, Vol. 379. Cambridge University Press, 177\u2013270."},{"key":"e_1_3_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ejc.2011.09.008"},{"key":"e_1_3_2_1_21_1","volume-title":"Algorithms and combinatorics","author":"Ne\u0161et\u0159il Jaroslav","unstructured":"Jaroslav Ne\u0161et\u0159il and Patrice Ossona de Mendez. 2012. Sparsity-Graphs, Structures, and Algorithms. Algorithms and combinatorics, Vol. 28. Springer."},{"key":"e_1_3_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00446-015-0251-x"},{"key":"e_1_3_2_1_23_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_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/3209108.3209136"},{"key":"e_1_3_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1017\/S0960129500070079"}],"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.3733507","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,13]],"date-time":"2025-06-13T14:25:29Z","timestamp":1749824729000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3732772.3733507"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,6,13]]},"references-count":25,"alternative-id":["10.1145\/3732772.3733507","10.1145\/3732772"],"URL":"https:\/\/doi.org\/10.1145\/3732772.3733507","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"}}]}}