## Abstract

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:

(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

(4) As a corollary, we can also

(5) In any graph of maximum degree Δ, we can find a Δ-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.

(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*(Δ) rounds.(5) In any graph of maximum degree Δ, we can find a Δ-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.

Original language | English |
---|---|

Title of host publication | Proceedings of the 43rd ACM Symposium on Principles of Distributed Computing |

Publisher | Association for Computing Machinery |

Publication date | 2024 |

Pages | 117-120 |

ISBN (Electronic) | 979-8-4007-0668-4/24/06 |

DOIs | |

Publication status | Published - 2024 |

## Keywords

- Distributed advice
- Distributed decompression
- Locality