PODC 2011 · 30th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing, San Jose, CA, USA, June 2011 · doi:10.1145/1993806.1993829

This work studies *decision problems* from the perspective of *nondeterministic distributed algorithms*. For a *yes*-instance there must exist a *proof* that can be verified with a distributed algorithm: all nodes must accept a valid proof, and at least one node must reject an invalid proof. We focus on *locally checkable proofs* that can be verified with a constant-time distributed algorithm.

For example, it is easy to prove that a graph is bipartite: the locally checkable proof gives a 2-colouring of the graph, which only takes 1 bit per node. However, it is more difficult to prove that a graph is *not* bipartite—it turns out that any locally checkable proof requires Ω(log *n*) bits per node.

In this work we classify graph problems according to their local proof complexity, i.e., how many bits per node are needed in a locally checkable proof. We establish tight or near-tight results for classical graph properties such as the chromatic number. We show that the proof complexities form a natural hierarchy of complexity classes: for many classical graph problems, the proof complexity is either 0, Θ(1), Θ(log *n*), or poly(*n*) bits per node. Among the most difficult graph properties are symmetric graphs, which require Ω(*n*^{2}) bits per node, and non-3-colourable graphs, which require Ω(*n*^{2}/log *n*) bits per node—any pure graph property admits a trivial proof of size *O*(*n*^{2}).

Cyril Gavoille and Pierre Fraigniaud (Eds.): *PODC’11, Proceedings of the 2011 ACM Symposium on Principles of Distributed Computing, June 6–8, 2011, San Jose, California, USA*, pages 159–168, ACM Press, New York, 2011

ISBN 978-1-4503-0719-2

- Mika Göös and Jukka Suomela: Locally checkable proofs in distributed computing ·
*Theory of Computing*12:#19, 2016