Near-Optimal Resilient Labeling Schemes

Keren Censor-Hillel, Einav Huberman · 2024

Read Near-Optimal Resilient Labeling Schemes by Keren Censor-Hillel, Einav Huberman (2024) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2412-01628.txt.

Description

Keren Censor-Hillel and Einav Huberman write a 2024 paper on keeping network labels useful even when some of them are lost. In a labeling scheme, a central oracle assigns each node of a graph a short label. Nodes then use their labels alone to answer tasks such as distance queries or proofs about the graph. Hardware faults or lost contact with the oracle can erase some labels.

The authors define a resilient scheme in two parts. First, the oracle rewrites any labeling into a tougher form. Then the nodes run a shared method to rebuild their first labels from the new ones, even with some labels missing. Their scheme restores labels with near-best possible cost. The work extends an earlier idea built only for proof labels to labeling schemes in general.

Catalog record

CREATORKeren Censor-Hillel, Einav Huberman
YEAR2024
COLLECTIONPAPERS
FORMATTXT
FILE SIZE68 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2412-01628

Browse the full library · About the Tower of Babel