A tight meta-theorem for LOCAL certification of MSO2 properties within bounded treewidth graphs
Linda Cook, Eun Jung Kim, Tomáš Masařík · 2025
Distributed networks are prone to errors so verifying their output is critical. We develop local certification protocols for graph properties in which nodes are given certificates that allow them to check whether the network as a whole satisfies some fixed property while only communicating with their local network. Instead of considering a specific problem and developing a local certification protocol tailor-made for the problem, we aim for generic protocols that can certify any property expressible in a certain logical framework.