Browse
- No file added yet -

# Brief Announcement: Local Advice and Local Decompression

conference contribution
posted on 2024-05-14, 09:17 authored by Alkida Balliu, Fabian Kuhn, Krzysztof Nowicki, Dennis Olivetti, Eva Rotenberg, Jukka Suomela
In 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.

## 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 }

## Categories

No categories selected

## Exports

RefWorks
BibTeX
Ref. manager
Endnote
DataCite
NLM
DC
figshare. credit for all your research.