2026-07-25T15:15:20Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:21277 2024-10-24T07:40:09Z ddc:004 open_access

Brief Announcement: Decreasing Verification Radius in Local Certification Křišťan, Jan Matyáš Sedláček, Josef Erik Local certification locally checkable proofs proof-labeling schemes graphs distributed 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. 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Jan Matyáš Křišťan and Josef Erik Sedláček 2024 Is Part Of LIPIcs, Volume 319, 38th International Symposium on Distributed Computing (DISC 2024) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.DISC.2024.49 urn:nbn:de:0030-drops-212773 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.DISC.2024.49 eng https://creativecommons.org/licenses/by/4.0/legalcode