Mika Göös · Jukka Suomela

Locally checkable proofs

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

authors’ version publisher’s version

Abstract

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 Ω(n2) bits per node, and non-3-colourable graphs, which require Ω(n2/log n) bits per node—any pure graph property admits a trivial proof of size O(n2).

Publication

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

Links

Journal Version

© ACM 2011 — This is the authors’ version of the work. It is posted here by permission of ACM for your personal use. Not for redistribution. The definitive version was published in Proc. 30th ACM SIGACT-SIGOPS Symposium on Principles of Distributed Computing. http://doi.acm.org/10.1145/1993806.1993829

This material is presented to ensure timely dissemination of scholarly and technical work. Copyright and all rights therein are retained by authors or by other copyright holders. All persons copying this information are expected to adhere to the terms and constraints invoked by each author’s copyright. In most cases, these works may not be reposted without the explicit permission of the copyright holder.