4 papers
Online Locality Meets Distributed Quantum Computing
Amirreza Akbari, Xavier Coiteux-Roy, Francesco d'Amore +8
We connect three distinct lines of research that have recently explored extensions of the classical LOCAL model of distributed computing: A. distributed quantum computing and non-s…
Mending Partial Solutions with Few Changes
Darya Melnyk, Jukka Suomela, Neven Villani
In this paper, we study the notion of mending, i.e. given a partial solution to a graph problem, we investigate how much effort is needed to turn it into a proper solution. For exa…
Locality in online, dynamic, sequential, and distributed graph algorithms
Amirreza Akbari, Navid Eslami, Henrik Lievonen +3
In this work, we give a unifying view of locality in four settings: distributed algorithms, sequential greedy algorithms, dynamic algorithms, and online algorithms. We introduce a…
Local Mending
Alkida Balliu, Juho Hirvonen, Darya Melnyk +3
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 o…