Theory of Computing ------------------- Title : Locally Checkable Proofs in Distributed Computing Authors : Mika Goos and Jukka Suomela Volume : 12 Number : 19 Pages : 1-33 URL : https://theoryofcomputing.org/articles/v012a019 Abstract -------- We study _decision problems_ related to _graph properties_ 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\$-coloring 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 \$\Omega(\log n)\$ bits per node. In this paper we classify graph properties 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 local proof complexities form a natural hierarchy of complexity classes: for many classical graph properties, the local proof complexity is either 0, Theta(1), Theta(log n), or poly(n) bits per node. Among the most difficult graph properties are proving that a graph is symmetric (has a non-trivial automorphism), which requires Omega(n^2) bits per node, and proving that a graph is _not_ 3-colorable, which requires Omega(n^2/log n) bits per node. Any property of connected graphs admits a trivial proof with O(n^2) bits per node. A preliminary version of this paper appeared in the Proceedings of the 30th ACM Symposium on Principles of Distributed Computing (PODC 2011) (DOI: 10.1145/1993806.1993829)