2024-06-17

# Brief Announcement: Local Advice and Local Decompression

## Zusammenfassung

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.

Konferenzbeitrag

ACM Symposium on Principles of Distributed Computing (PODC)

Veröffentlichungsdatum

2024-06-17

Letztes Änderungsdatum

2024-07-18