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.
ACM Symposium on Principles of Distributed Computing (PODC)
2024-06-17
2024-07-18