Brief Announcement: Local Advice and Local Decompression
Alkida Balliu, Sebastian Brandt, Fabian Kühn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela · 2024
In this work we study local computation with advice: the goal is to solve a graph problem Π with a distributed algorithm in f (Δ) communication rounds, for some function f that only depends on the maximum degree Δ of the graph, and the key question is how many bits of advice per node are needed. Our main results are: