paper.pdf (471.76 kB)

# Brief Announcement: Local Advice and Local Decompression

conference contribution

posted on 2024-05-14, 09:17 authored by Alkida Balliu, Sebastian BrandtSebastian Brandt, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka SuomelaIn this work we study local computation with advice: the goal is to solve a graph problem $\Pi$ with a distributed algorithm in $f(\Delta)$ communication rounds, for some function $f$ that only depends on the maximum degree $\Delta$ of the graph, and the key question is how many bits of advice per node are needed. Our main results are:
1. Any locally checkable labeling problem (LCL) can be solved in graphs with sub-exponential growth with only $1$ bit of advice per node. Moreover, we can make the set of nodes that carry advice bits arbitrarily sparse.
2. The assumption of sub-exponential growth is necessary: assuming the Exponential-Time Hypothesis (ETH), there are LCLs that cannot be solved in general with any constant number of bits per node.
3. In any graph we can find an almost-balanced orientation (indegrees and outdegrees differ by at most one) with $1$ bit of advice per node, and again we can make the advice arbitrarily sparse.
4. As a corollary, we can also compress an arbitrary subset of edges so that a node of degree $d$ stores only $d/2 + 2$ bits, and we can decompress it locally, in $f(\Delta)$ rounds.
5. In any graph of maximum degree $\Delta$, we can find a $\Delta$-coloring (if it exists) with $1$ bit of advice per node, and again, we can make the advice arbitrarily sparse.
6. In any $3$-colorable graph, we can find a $3$-coloring with $1$ bit of advice per node. Here, it remains open whether we can make the advice arbitrarily sparse.

## History

## Primary Research Area

- Algorithmic Foundations and Cryptography

## Name of Conference

ACM Symposium on Principles of Distributed Computing (PODC)## BibTeX

@conference{Balliu:Brandt:Kuhn:Nowicki:Olivetti:Rotenberg:Suomela:2024, title = "Brief Announcement: Local Advice and Local Decompression", author = "Balliu, Alkida" AND "Brandt, Sebastian" AND "Kuhn, Fabian" AND "Nowicki, Krzysztof" AND "Olivetti, Dennis" AND "Rotenberg, Eva" AND "Suomela, Jukka", year = 2024, month = 6 }## Usage metrics

## Categories

No categories selected## Licence

## Exports

RefWorks

BibTeX

Ref. manager

Endnote

DataCite

NLM

DC