CISPA
Browse
paper.pdf (471.76 kB)

Brief Announcement: Local Advice and Local Decompression

Download (471.76 kB)
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 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.

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