Decreasing verification radius in local certification
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866917754148225024 |
|---|---|
| author | Feuilloley, Laurent Janoušek, Jan Křišťan, Jan Matyáš Sedláček, Josef Erik |
| author_facet | Feuilloley, Laurent Janoušek, Jan Křišťan, Jan Matyáš Sedláček, Josef Erik |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2408_10757 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Decreasing verification radius in local certification Feuilloley, Laurent Janoušek, Jan Křišťan, Jan Matyáš Sedláček, Josef Erik Distributed, Parallel, and Cluster Computing 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. |
| title | Decreasing verification radius in local certification |
| topic | Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2408.10757 |