aalto1 untyped-item.component.html
Locally checkable proofs in distributed computing
Loading...
Files
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A1 Alkuperäisartikkeli tieteellisessä aikakauslehdessä
This publication is imported from Aalto University research portal.
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
View publication in the Research portal (opens in new window)
View/Open full text file from the Research portal (opens in new window)
Unless otherwise stated, all rights belong to the author. You may download, display and print this publication for Your own personal use. Commercial use is prohibited.
Authors
Date
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
THEORY OF COMPUTING, Volume 12, pp. 1–33
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 Ω(logn) 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 neartight 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, Θ(1), Θ(logn), 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 Ω(n2) bits per node, and proving that a graph is not 3-colorable, which requires Ω(n2=logn) bits per node. Any property of connected graphs admits a trivial proof with O(n2) bits per node.
Description
Keywords
Other note
Citation
Göös, M & Suomela, J 2016, 'Locally checkable proofs in distributed computing', THEORY OF COMPUTING, vol. 12, 19, pp. 1–33. https://doi.org/10.4086/toc.2016.v012a019