@inproceedings{7f5f2f167b9c4dd694900ca26b6c309d,
title = "Descriptive Complexity for Distributed Computing with Circuits",
abstract = "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.",
keywords = "Descriptive complexity, distributed computing, graph coloring, logic",
author = "Veeti Ahvonen and Damian Heiman and Lauri Hella and Antti Kuusisto",
note = "Funding Information: Funding Antti Kuusisto and Veeti Ahvonen were supported by the Academy of Finland project Theory of computational logics, grant numbers 352419, 352420, 353027, 324435, 328987. Antti Kuusisto was also supported by the Academy of Finland consortium project Explaining AI via Logic (XAILOG), grant number 345612. Veeti Ahvonen was also supported by the Vilho, Yrj{\"o} and Kalle V{\"a}is{\"a}l{\"a} Foundation of the Finnish Academy of Science and Letters. Publisher Copyright: {\textcopyright} Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto;; International Symposium on Mathematical Foundations of Computer Science ; Conference date: 28-08-2023 Through 01-09-2023",
year = "2023",
month = aug,
doi = "10.4230/LIPIcs.MFCS.2023.9",
language = "English",
series = "Leibniz International Proceedings in Informatics, LIPIcs",
publisher = "Schloss Dagstuhl - Leibniz-Zentrum f{\"u}r Informatik",
editor = "Jerome Leroux and Sylvain Lombardy and David Peleg",
booktitle = "48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023",
}