Reductions in local certification
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2025
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913915268497408 |
|---|---|
| author | Esperet, Louis Zeitoun, Sébastien |
| author_facet | Esperet, Louis Zeitoun, Sébastien |
| contents | Local certification is a topic originating from distributed computing, where a prover tries to convince the vertices of a graph $G$ that $G$ satisfies some property $\mathcal{P}$. To convince the vertices, the prover gives a small piece of information, called certificate, to each vertex, and the vertices then decide whether the property $\mathcal{P}$ is satisfied by just looking at their certificate and the certificates of their neighbors. When studying a property $\mathcal{P}$ in the perspective of local certification, the aim is to find the optimal size of the certificates needed to certify $\mathcal{P}$, which can be viewed a measure of the local complexity of $\mathcal{P}$.
A certification scheme is considered to be efficient if the size of the certificates is polylogarithmic in the number of vertices. While there have been a number of meta-theorems providing efficient certification schemes for general graph classes, the proofs of the lower bounds on the size of the certificates are usually very problem-dependent.
In this work, we introduce a notion of hardness reduction in local certification, and show that we can transfer a lower bound on the certificates for a property $\mathcal{P}$ to a lower bound for another property $\mathcal{P}'$, via a (local) hardness reduction from $\mathcal{P}$ to $\mathcal{P}'$. We then give a number of applications in which we obtain polynomial lower bounds for many classical properties using such reductions. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2502_01551 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Reductions in local certification Esperet, Louis Zeitoun, Sébastien Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms Combinatorics Local certification is a topic originating from distributed computing, where a prover tries to convince the vertices of a graph $G$ that $G$ satisfies some property $\mathcal{P}$. To convince the vertices, the prover gives a small piece of information, called certificate, to each vertex, and the vertices then decide whether the property $\mathcal{P}$ is satisfied by just looking at their certificate and the certificates of their neighbors. When studying a property $\mathcal{P}$ in the perspective of local certification, the aim is to find the optimal size of the certificates needed to certify $\mathcal{P}$, which can be viewed a measure of the local complexity of $\mathcal{P}$. A certification scheme is considered to be efficient if the size of the certificates is polylogarithmic in the number of vertices. While there have been a number of meta-theorems providing efficient certification schemes for general graph classes, the proofs of the lower bounds on the size of the certificates are usually very problem-dependent. In this work, we introduce a notion of hardness reduction in local certification, and show that we can transfer a lower bound on the certificates for a property $\mathcal{P}$ to a lower bound for another property $\mathcal{P}'$, via a (local) hardness reduction from $\mathcal{P}$ to $\mathcal{P}'$. We then give a number of applications in which we obtain polynomial lower bounds for many classical properties using such reductions. |
| title | Reductions in local certification |
| topic | Distributed, Parallel, and Cluster Computing Discrete Mathematics Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2502.01551 |