What Can Be Certified Compactly? Compact local certification of MSO properties in tree-like graphs
Laurent Feuilloley, Nicolas Bousquet, Théo Pierron · 2022
Local certification consists in assigning labels (called certificates) to the nodes of a network to certify a property of the network or the correctness of a data structure distributed on the network. The verification of this certification must be local: a node typically sees only its neighbors in the network. The main measure of performance of a certification is the size of its certificates.