Descriptive Complexity for Distributed Computing with Circuits

Veeti Ahvonen; Damian Heiman; Lauri Hella; Antti Kuusisto

doi:10.4230/LIPIcs.MFCS.2023.9

Descriptive Complexity for Distributed Computing with Circuits

Veeti Ahvonen
, Damian Heiman
, Lauri Hella
, Antti Kuusisto

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

Abstrakti

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.

Alkuperäiskieli	englanti
Otsikko	48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023
Toimittajat	Jerome Leroux, Sylvain Lombardy, David Peleg
Kustantaja	Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing
Julkaisupäivä	elok. 2023
Artikkeli no	9
ISBN (elektroninen)	978-3-95977-292-1
DOI - pysyväislinkit	https://doi.org/10.4230/LIPIcs.MFCS.2023.9
Tila	Julkaistu - elok. 2023
Julkaistu ulkoisesti	Kyllä
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisuussa
Tapahtuma	International Symposium on Mathematical Foundations of Computer Science - Bordeaux, Ranska Kesto: 28 elok. 2023 → 1 syysk. 2023 Konferenssinumero: 48

Julkaisusarja

Nimi	Leibniz International Proceedings in Informatics, LIPIcs
Vuosikerta	272
ISSN (painettu)	1868-8969

Lisätietoja

Publisher Copyright:
© Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto;

Tieteenalat

113 Tietojenkäsittely- ja informaatiotieteet

Pääsy asiakirjaan

10.4230/LIPIcs.MFCS.2023.9Lisenssi: CC BY

Siteeraa tätä

Ahvonen, V., Heiman, D., Hella, L., & Kuusisto, A. (2023). Descriptive Complexity for Distributed Computing with Circuits. teoksessa J. Leroux, S. Lombardy, & D. Peleg (Toimittajat), 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023 Artikkeli 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 272). Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. https://doi.org/10.4230/LIPIcs.MFCS.2023.9

Ahvonen, Veeti ; Heiman, Damian ; Hella, Lauri et al. / Descriptive Complexity for Distributed Computing with Circuits. 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. Toimittaja / Jerome Leroux ; Sylvain Lombardy ; David Peleg. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. (Leibniz International Proceedings in Informatics, LIPIcs).

@inproceedings{ca82b37e14994a639536ccc38e31dd6e,

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, 113 Computer and information sciences",

author = "Veeti Ahvonen and Damian Heiman and Lauri Hella and Antti Kuusisto",

note = "Publisher Copyright: {\textcopyright} Veeti Ahvonen, Damian Heiman, Lauri Hella, and Antti Kuusisto;; International Symposium on Mathematical Foundations of Computer Science, MFCS ; 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 fur Informatik GmbH, Dagstuhl Publishing",

editor = "Jerome Leroux and Sylvain Lombardy and David Peleg",

booktitle = "48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023",

address = "Germany",

}

Ahvonen, V, Heiman, D, Hella, L & Kuusisto, A 2023, Descriptive Complexity for Distributed Computing with Circuits. julkaisussa J Leroux, S Lombardy & D Peleg (toim), 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023., 9, Leibniz International Proceedings in Informatics, LIPIcs, Vuosikerta 272, Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, International Symposium on Mathematical Foundations of Computer Science, Bordeaux, Ranska, 28/08/2023. https://doi.org/10.4230/LIPIcs.MFCS.2023.9

Descriptive Complexity for Distributed Computing with Circuits. / Ahvonen, Veeti; Heiman, Damian; Hella, Lauri et al.
48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. toim. / Jerome Leroux; Sylvain Lombardy; David Peleg. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing, 2023. 9 (Leibniz International Proceedings in Informatics, LIPIcs; Vuosikerta 272).

Tutkimustuotos: Artikkeli kirjassa/raportissa/konferenssijulkaisussa › Konferenssiartikkeli › Tieteellinen › vertaisarvioitu

TY - GEN

T1 - Descriptive Complexity for Distributed Computing with Circuits

AU - Ahvonen, Veeti

AU - Heiman, Damian

AU - Hella, Lauri

AU - Kuusisto, Antti

N1 - Conference code: 48

PY - 2023/8

Y1 - 2023/8

N2 - 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.

AB - 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.

KW - Descriptive complexity

KW - distributed computing

KW - graph coloring

KW - logic

KW - 113 Computer and information sciences

U2 - 10.4230/LIPIcs.MFCS.2023.9

DO - 10.4230/LIPIcs.MFCS.2023.9

M3 - Conference contribution

AN - SCOPUS:85171448265

T3 - Leibniz International Proceedings in Informatics, LIPIcs

BT - 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023

A2 - Leroux, Jerome

A2 - Lombardy, Sylvain

A2 - Peleg, David

PB - Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing

T2 - International Symposium on Mathematical Foundations of Computer Science

Y2 - 28 August 2023 through 1 September 2023

ER -

Ahvonen V, Heiman D, Hella L, Kuusisto A. Descriptive Complexity for Distributed Computing with Circuits. julkaisussa Leroux J, Lombardy S, Peleg D, toimittajat, 48th International Symposium on Mathematical Foundations of Computer Science, MFCS 2023. Schloss Dagstuhl- Leibniz-Zentrum fur Informatik GmbH, Dagstuhl Publishing. 2023. 9. (Leibniz International Proceedings in Informatics, LIPIcs). doi: 10.4230/LIPIcs.MFCS.2023.9