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
| CREATOR | Keren Censor-Hillel, Einav Huberman |
|---|---|
| YEAR | 2024 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 68 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2412-01628