2025/02/03 by Louis Esperet, Esperet, Louis, Sébastien Zeitoun +1 · 1 citation
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #Cryptography and Data Security #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #Distributed #FOS: Computer and information sciences #FOS: Mathematics #Parallel #and Cluster Computing (cs.DC)
paper · pdf · doi:10.48550/arxiv.2502.01551
openalex publication_date 2025/02/03 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 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 P is satisfied by just looking at their certificate and the certificates of their neighbors. When studying a property P in the perspective of local certification, the aim is to find the optimal size of the certificates needed to certify P, which can be viewed a measure of the local complexity of 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 P to a lower bound for another property P', via a (local) hardness reduction from P to P'. We then give a number of applications in which we obtain polynomial lower bounds for many classical properties using such reductions.