pdf icon
Volume 12 (2016) Article 19 pp. 1-33
Locally Checkable Proofs in Distributed Computing
Received: August 20, 2012
Revised: November 3, 2016
Published: November 29, 2016
Download article from ToC site:
[PDF (542K)]    [PS (2632K)]    [PS.GZ (567K)]
[Source ZIP]
Keywords: nondeterminism, distributed computing, locality, graphs
ACM Classification: C.2.4, F.1.3
AMS Classification: 68M14, 68Q15, 68Q25, 68Q85, 03F20

Abstract: [Plain Text Version]

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 $\text{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).