Decreasing Verification Radius in Local Certification

Josef Erik Sedláček, Jan Matyáš Křišťan, Laurent Feuilloley, Jan Janoušek.

Theoretical Computer Science 2025.
doi:10.1016/j.tcs.2025.115520

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 neighborhood 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.

This work was done mostly by Josef Erik Sedláček and Jan Matyáš Křišťan, two PhD students from CTU in Prague, who came to me with the idea. I basically only contributed the part about shaving logs in paths. The paper was presented by Matyáš at Algowin 2024 in London.