Local Mending

Alkida Balliu; Juho Hirvonen; Darya Melnyk; Dennis Olivetti; Joel Rybicki; Jukka Suomela

doi:10.1007/978-3-031-09993-9_1

Local Mending

Alkida Balliu, Juho Hirvonen, Darya Melnyk^*, Dennis Olivetti, Joel Rybicki, Jukka Suomela

^*Tämän työn vastaava kirjoittaja

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

2 Sitaatiot (Scopus)

Abstrakti

In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log^∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log^∗n), there is always a restriction Π^′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

Alkuperäiskieli	Englanti
Otsikko	Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings
Toimittajat	Merav Parter
Kustantaja	Springer
Sivut	1-20
Sivumäärä	20
ISBN (painettu)	978-3-031-09992-2
DOI - pysyväislinkit	https://doi.org/10.1007/978-3-031-09993-9_1
Tila	Julkaistu - 2022
OKM-julkaisutyyppi	A4 Artikkeli konferenssijulkaisussa
Tapahtuma	International Colloquium on Structural Information and Communication Complexity - Paderborn, Saksa Kesto: 27 kesäk. 2022 → 29 kesäk. 2022 Konferenssinumero: 29

Julkaisusarja

Nimi	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Kustantaja	Springer
Vuosikerta	13298 LNCS
ISSN (painettu)	0302-9743
ISSN (elektroninen)	1611-3349

Conference

Conference	International Colloquium on Structural Information and Communication Complexity
Lyhennettä	SIROCCO
Maa/Alue	Saksa
Kaupunki	Paderborn
Ajanjakso	27/06/2022 → 29/06/2022

Pääsy asiakirjaan

10.1007/978-3-031-09993-9_1

https://arxiv.org/abs/2102.08703

Muut tiedostot ja linkit

Linkki julkaisuun Scopuksessa

LocalMend /Suomela: Local Checking, Solving, and Mending—New Perspectives of Distributed Computing (LocalMend)
Suomela, J., Lievonen, H., Melnyk, D., Vahidi, H., Studeny, J. & Akbari, A.
01/09/2020 → 31/08/2024
Projekti: Academy of Finland: Other research funding
Kohti hajautettujen verkkoalgoritmien kompleksisuusteoriaa
Hirvonen, J.
01/09/2018 → 31/10/2021
Projekti: Academy of Finland: Other research funding

Siteeraa tätä

Balliu, A., Hirvonen, J., Melnyk, D., Olivetti, D., Rybicki, J., & Suomela, J. (2022). Local Mending. teoksessa M. Parter (Toimittaja), Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings (Sivut 1-20). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 13298 LNCS). Springer. https://doi.org/10.1007/978-3-031-09993-9_1

Balliu, Alkida ; Hirvonen, Juho ; Melnyk, Darya et al. / Local Mending. Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. Toimittaja / Merav Parter. Springer, 2022. Sivut 1-20 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{11994d7a774b471e90c53ed8a56a3ca2,

title = "Local Mending",

abstract = "In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.",

keywords = "Distributed algorithms, Dynamic algorithms, Fault tolerance, LCL problems, Mendability, Parallel algorithms",

author = "Alkida Balliu and Juho Hirvonen and Darya Melnyk and Dennis Olivetti and Joel Rybicki and Jukka Suomela",

note = "| openaire: EC/H2020/840605/EU//CoCoNat Funding Information: Acknowledgements. This project has received funding from the European Union{\textquoteright}s Horizon 2020 research and innovation programme under the Marie Sk lodowska-Curie grant agreement No 840605. This work was supported in part by the Academy of Finland, Grants 314888 and 333837. The authors would also like to thank David Harris, Neven Villani, and the anonymous reviewers for their very helpful comments and feedback on previous versions of this work. Publisher Copyright: {\textcopyright} 2022, Springer Nature Switzerland AG.; International Colloquium on Structural Information and Communication Complexity, SIROCCO ; Conference date: 27-06-2022 Through 29-06-2022",

year = "2022",

doi = "10.1007/978-3-031-09993-9_1",

language = "English",

isbn = "978-3-031-09992-2",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer",

pages = "1--20",

editor = "Merav Parter",

booktitle = "Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings",

address = "Germany",

}

Balliu, A, Hirvonen, J, Melnyk, D, Olivetti, D, Rybicki, J & Suomela, J 2022, Local Mending. julkaisussa M Parter (Toimittaja), Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vuosikerta 13298 LNCS, Springer, Sivut 1-20, International Colloquium on Structural Information and Communication Complexity, Paderborn, Saksa, 27/06/2022. https://doi.org/10.1007/978-3-031-09993-9_1

Local Mending. / Balliu, Alkida; Hirvonen, Juho; Melnyk, Darya et al.
Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. toim. / Merav Parter. Springer, 2022. s. 1-20 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vuosikerta 13298 LNCS).

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussa › Conference article in proceedings › Scientific › vertaisarvioitu

TY - GEN

T1 - Local Mending

AU - Balliu, Alkida

AU - Hirvonen, Juho

AU - Melnyk, Darya

AU - Olivetti, Dennis

AU - Rybicki, Joel

AU - Suomela, Jukka

N1 - Conference code: 29

PY - 2022

Y1 - 2022

N2 - In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

AB - In this work we introduce the graph-theoretic notion of mendability: for each locally checkable graph problem we can define its mending radius, which captures the idea of how far one needs to modify a partial solution in order to “patch a hole.” We explore how mendability is connected to the existence of efficient algorithms, especially in distributed, parallel, and fault-tolerant settings. It is easy to see that O(1)-mendable problems are also solvable in O(log∗n) rounds in the LOCAL model of distributed computing. One of the surprises is that in paths and cycles, a converse also holds in the following sense: if a problem Π can be solved in O(log∗n), there is always a restriction Π′⊆ Π that is still efficiently solvable but that is also O(1)-mendable. We also explore the structure of the landscape of mendability. For example, we show that in trees, the mending radius of any locally checkable problem is O(1), Θ(log n), or Θ(n), while in general graphs the structure is much more diverse.

KW - Distributed algorithms

KW - Dynamic algorithms

KW - Fault tolerance

KW - LCL problems

KW - Mendability

KW - Parallel algorithms

UR - http://www.scopus.com/inward/record.url?scp=85134351744&partnerID=8YFLogxK

U2 - 10.1007/978-3-031-09993-9_1

DO - 10.1007/978-3-031-09993-9_1

M3 - Conference article in proceedings

AN - SCOPUS:85134351744

SN - 978-3-031-09992-2

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 1

EP - 20

BT - Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings

A2 - Parter, Merav

PB - Springer

T2 - International Colloquium on Structural Information and Communication Complexity

Y2 - 27 June 2022 through 29 June 2022

ER -

Balliu A, Hirvonen J, Melnyk D, Olivetti D, Rybicki J, Suomela J. Local Mending. julkaisussa Parter M, toimittaja, Structural Information and Communication Complexity - 29th International Colloquium, SIROCCO 2022, Proceedings. Springer. 2022. s. 1-20. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-031-09993-9_1

Local Mending

Abstrakti

Julkaisusarja

Conference

Pääsy asiakirjaan

Muut tiedostot ja linkit

Sormenjälki

Projektit

LocalMend /Suomela: Local Checking, Solving, and Mending—New Perspectives of Distributed Computing (LocalMend)

Kohti hajautettujen verkkoalgoritmien kompleksisuusteoriaa

Siteeraa tätä