Decreasing verification radius in local certification
<|reference_start|>Decreasing verification radius in local certification: This paper deals with local certification, specifically locally checkable proofs: given a graph property, the task is to certify whether a graph satisfies the property. The verification of this certification needs to be done locally without the knowledge of the whole graph. More precisely, a distributed algorithm, called a verifier, is executed on each vertex. The verifier observes the local neighborhood up to a constant distance and either accepts or rejects. We examine the trade-off between the visibility radius and the size of certificates. We describe a procedure that decreases the radius by encoding the neighbourhood of each vertex into its certificate. We also provide a corresponding lower bound on the required certificate size increase, showing that such an approach is close to optimal.<|reference_end|>
@article{feuilloley2024decreasing,
    title={Decreasing verification radius in local certification},
    author={Laurent Feuilloley, Jan Janouv{s}ek, Jan Maty'av{s}
  Kv{r}iv{s}v{t}an, Josef Erik Sedl'av{c}ek},
    journal={arXiv preprint arXiv:2408.10757},
    year={2024},
    archivePrefix={arXiv},
    eprint={2408.10757},
    primaryClass={cs.DC}
}