2026-07-22T06:50:06Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:18543 2024-03-06T11:02:04Z ddc:004 open_access

Descriptive Complexity for Distributed Computing with Circuits Ahvonen, Veeti Heiman, Damian Hella, Lauri Kuusisto, Antti Descriptive complexity distributed computing logic graph coloring We consider distributed algorithms in the realistic scenario where distributed message passing is operated by circuits. We show that within this setting, modal substitution calculus MSC precisely captures the expressive power of circuits. The result is established via constructing translations that are highly efficient in relation to size. We also observe that the coloring algorithm based on Cole-Vishkin can be specified by logarithmic size programs (and thus also logarithmic size circuits) in the bounded-degree scenario. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Veeti Ahvonen and Damian Heiman and Lauri Hella and Antti Kuusisto 2023 Is Part Of LIPIcs, Volume 272, 48th International Symposium on Mathematical Foundations of Computer Science (MFCS 2023) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.MFCS.2023.9 urn:nbn:de:0030-drops-185433 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.MFCS.2023.9 eng https://creativecommons.org/licenses/by/4.0/legalcode