Decreasing verification radius in local certification

DOI10.1016/J.TCS.2025.115520MaRDI QIDQ6903535zbMATH OpenFDO

Authors Laurent Feuilloley, Jan Janoušek, Jan Matyáš Křišt'an, Josef Erik Sedláček

Publication date 10 November 2025

Published in Theoretical Computer Science (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.TCS.2025.115520

zbMATH Keywords

distributed computinggraphslocal certificationlocally checkable proofsproof-labeling schemesself-stabilization

Mathematics Subject Classification ID

Modes of computation (nondeterministic, parallel, interactive, probabilistic, etc.) (68Q10) Graph theory (including graph drawing) in computer science (68R10) Distributed algorithms (68W15)

Cites work

• A meta-theorem for distributed certification
• Brief announcement: Local advice and local decompression
• Distributed Computing: A Locality-Sensitive Approach
• Distributed verification of minimum spanning trees
• scientific article; zbMATH DE number 7832762 (Why is no real title available?)
• Introduction to Distributed Self-Stabilizing Algorithms
• Introduction to local certification
• Local certification of local properties: tight bounds, trade-offs and new parameters
• Locally checkable proofs in distributed computing
• Proof labeling schemes
• Redundancy in distributed proofs
• Self-stabilization
• Space-time tradeoffs for distributed verification
• Towards a complexity theory for local distributed computing
• What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs

This page was built for publication: Decreasing verification radius in local certification

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6903535)