{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,12]],"date-time":"2026-03-12T11:21:08Z","timestamp":1773314468626,"version":"3.50.1"},"reference-count":20,"publisher":"Oxford University Press (OUP)","issue":"5","license":[{"start":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T00:00:00Z","timestamp":1737072000000},"content-version":"vor","delay-in-days":1,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0\/"}],"content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2025,6,11]]},"abstract":"<jats:title>Abstract<\/jats:title>\n               <jats:p>We investigate distributed computing with identifiers in the realistic scenario where the local computations in a distributed message passing setting are operated by Boolean circuits. We call this framework the message passing circuit model. We capture the expressive power of the model with a recursive rule-based logic called modal substitution calculus MSC. The result is established via constructing translations that are highly efficient in relation to size and computation time. In particular, the worst size blow-up is quadratic and becomes linear in the bounded-degree scenario. Computation time delays are similarly modest. As a concrete demonstration of how our setting works, we establish that a very fast coloring algorithm based on Cole\u2013Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario.<\/jats:p>","DOI":"10.1093\/logcom\/exae087","type":"journal-article","created":{"date-parts":[[2025,1,17]],"date-time":"2025-01-17T03:57:48Z","timestamp":1737086268000},"source":"Crossref","is-referenced-by-count":1,"title":["Descriptive complexity for distributed computing with circuits"],"prefix":"10.1093","volume":"35","author":[{"given":"Veeti","family":"Ahvonen","sequence":"first","affiliation":[{"name":"Mathematics Research Centre , Tampere University, 33720, Tampere,","place":["Finland"]}]},{"given":"Damian","family":"Heiman","sequence":"additional","affiliation":[{"name":"Mathematics Research Centre , Tampere University, 33720, Tampere,","place":["Finland"]}]},{"given":"Lauri","family":"Hella","sequence":"additional","affiliation":[{"name":"Mathematics Research Centre , Tampere University, 33720, Tampere,","place":["Finland"]}]},{"given":"Antti","family":"Kuusisto","sequence":"additional","affiliation":[{"name":"Mathematics Research Centre , Tampere University, 33720, Tampere,","place":["Finland"]}]}],"member":"286","published-online":{"date-parts":[[2025,1,16]]},"reference":[{"key":"2025061108221096400_ref1","article-title":"Logical characterizations of recurrent graph neural networks with reals and floats","volume-title":"The Thirty-Eighth Annual Conference on Neural Information Processing Systems, Vancouver, Canada","author":"Ahvonen","year":"2024"},{"key":"2025061108221096400_ref2","article-title":"The logical expressiveness of graph neural networks","volume-title":"8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia","author":"Barcel\u00f3","year":"2020"},{"key":"2025061108221096400_ref3","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-031-02009-4_3","article-title":"Distributed graph coloring","volume":"11","author":"Barenboim","year":"2013","journal-title":"Synthesis Lectures on Distributed Computing Theory"},{"key":"2025061108221096400_ref4","first-page":"115","article-title":"Identifiers in registers\u2014describing network algorithms with logic","volume-title":"Foundations of Software Science and Computation Structures\u201422nd International Conference, FOSSACS 2019, Held as Part of the European Joint Conferences on Theory and Practice of Software, ETAPS 2019, Prague, Czech Republic, April 6\u201311, 2019, Proceedings, Volume 11425 of Lecture Notes in Computer Science","author":"Bollig","year":"2019"},{"key":"2025061108221096400_ref5","doi-asserted-by":"crossref","first-page":"32","DOI":"10.1016\/S0019-9958(86)80023-7","article-title":"Deterministic coin tossing with applications to optimal parallel list ranking","volume":"70","author":"Cole","year":"1986","journal-title":"Information and Control"},{"key":"2025061108221096400_ref6","doi-asserted-by":"crossref","first-page":"434","DOI":"10.1137\/0401044","article-title":"Parallel symmetry-breaking in sparse graphs","volume":"1","author":"Goldberg","year":"1988","journal-title":"SIAM Journal on Discrete Mathematics"},{"key":"2025061108221096400_ref7","doi-asserted-by":"crossref","first-page":"1","DOI":"10.1109\/LICS52264.2021.9470677","article-title":"The logic of graph neural networks","volume-title":"36th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2021","author":"Grohe","year":"2021"},{"key":"2025061108221096400_ref8","first-page":"1","article-title":"The descriptive complexity of graph neural networks","author":"Grohe","year":"2023","journal-title":"38th Annual ACM\/IEEE Symposium on Logic in Computer Science, LICS 2023, Boston, MA, USA, June 26-29, 2023"},{"key":"2025061108221096400_ref9","first-page":"185","article-title":"Weak models of distributed computing, with connections to modal logic","volume-title":"ACM Symposium on Principles of Distributed Computing, PODC \u201812, Madeira, Portugal","author":"Hella","year":"2012"},{"key":"2025061108221096400_ref10","doi-asserted-by":"crossref","first-page":"31","DOI":"10.1007\/s00446-013-0202-3","article-title":"Weak models of distributed computing, with connections to modal logic","volume":"28","author":"Hella","year":"2015","journal-title":"Distributed Computing"},{"key":"2025061108221096400_ref11","doi-asserted-by":"crossref","DOI":"10.4171\/icm2022\/162","article-title":"Theory of graph neural networks: Representation and learning","volume-title":"International Congress of Mathematicians: 2022 July 6\u201314","author":"Jegelka","year":"2023"},{"key":"2025061108221096400_ref12","first-page":"452","article-title":"Modal logic and distributed message passing automata","volume-title":"Computer Science Logic 2013 (CSL 2013), Torino, Italy, Volume 23 of Leibniz International Proceedings in Informatics (LIPIcs)","author":"Kuusisto","year":"2013"},{"key":"2025061108221096400_ref13","first-page":"147","article-title":"Infinite networks, halting and local algorithms","volume-title":"Proceedings Fifth International Symposium on Games, Automata, Logics and Formal Verification, GandALF, 2014, Verona, Italy, Volume 161 of EPTCS","author":"Kuusisto","year":"2014"},{"key":"2025061108221096400_ref14","first-page":"29","volume-title":"Logic and Complexity in Distributed Computing","author":"Lempi\u00e4inen","year":"2019"},{"key":"2025061108221096400_ref15","doi-asserted-by":"crossref","DOI":"10.1007\/978-3-662-07003-1","volume-title":"Elements of Finite Model Theory","author":"Libkin","year":"2004"},{"key":"2025061108221096400_ref16","article-title":"What graph neural networks cannot learn: depth vs width","volume-title":"8th International Conference on Learning Representations, ICLR 2020, Addis Ababa, Ethiopia, April 26\u201330, 2020","author":"Loukas","year":"2020"},{"key":"2025061108221096400_ref17","first-page":"100:1","article-title":"Asynchronous distributed automata: a characterization of the modal mu-fragment","volume-title":"44th International Colloquium on Automata, Languages, and Programming, ICALP 2017, Warsaw, Poland, Volume 80 of LIPIcs","author":"Reiter","year":"2017"},{"key":"2025061108221096400_ref18","volume-title":"Distributed Automata and Logic (Automates Distribu\u00e9s et Logique)","author":"Reiter","year":"2017"},{"key":"2025061108221096400_ref19","doi-asserted-by":"crossref","first-page":"333","DOI":"10.1137\/1.9781611976700.38","article-title":"Random features strengthen graph neural networks","volume-title":"Proceedings of the 2021 SIAM International Conference on Data Mining (SDM)","author":"Sato","year":"2021"},{"key":"2025061108221096400_ref20","volume-title":"Introduction to Circuit Complexity: A Uniform Approach","author":"Vollmer","year":"2013"}],"container-title":["Journal of Logic and Computation"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/5\/exae087\/61462339\/exae087.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/academic.oup.com\/logcom\/article-pdf\/35\/5\/exae087\/61462339\/exae087.pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,11]],"date-time":"2025-06-11T12:22:24Z","timestamp":1749644544000},"score":1,"resource":{"primary":{"URL":"https:\/\/academic.oup.com\/logcom\/article\/doi\/10.1093\/logcom\/exae087\/7958734"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2025,1,16]]},"references-count":20,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2025,6,11]]}},"URL":"https:\/\/doi.org\/10.1093\/logcom\/exae087","relation":{},"ISSN":["0955-792X","1465-363X"],"issn-type":[{"value":"0955-792X","type":"print"},{"value":"1465-363X","type":"electronic"}],"subject":[],"published-other":{"date-parts":[[2025,7]]},"published":{"date-parts":[[2025,1,16]]},"article-number":"exae087"}}