Feuilloley, Laurent ;
Fraigniaud, Pierre ;
Hirvonen, Juho
A Hierarchy of Local Decision
Abstract
We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on socalled distributed graph automata. We show that, by using distributed decision mechanisms based on the interaction between a prover and a disprover, the size of the certificates distributed to the nodes for certifying a given network property can be drastically reduced. For instance, we prove that minimum spanning tree can be certified with O(log(n))bit certificates in nnode graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires Omega(log^2(n))bit certificates if only the prover can act. The improvement can even be exponential for some simple graph properties.
For instance, it is known that certifying the existence of a nontrivial automorphism requires Omega(n^2) bits if only the prover can act. We show that there is a protocol with two interactions between the prover and the disprover enabling to certify nontrivial automorphism with O(log(n)) bit certificates. These results are achieved by defining and analysing a local hierarchy of decision which generalizes the classical notions of prooflabelling schemes and locally checkable proofs.
BibTeX  Entry
@InProceedings{feuilloley_et_al:LIPIcs:2016:6253,
author = {Laurent Feuilloley and Pierre Fraigniaud and Juho Hirvonen},
title = {{A Hierarchy of Local Decision}},
booktitle = {43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)},
pages = {118:1118:15},
series = {Leibniz International Proceedings in Informatics (LIPIcs)},
ISBN = {9783959770132},
ISSN = {18688969},
year = {2016},
volume = {55},
editor = {Ioannis Chatzigiannakis, Michael Mitzenmacher, Yuval Rabani, and Davide Sangiorgi},
publisher = {Schloss DagstuhlLeibnizZentrum fuer Informatik},
address = {Dagstuhl, Germany},
URL = {http://drops.dagstuhl.de/opus/volltexte/2016/6253},
URN = {urn:nbn:de:0030drops62536},
doi = {10.4230/LIPIcs.ICALP.2016.118},
annote = {Keywords: Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality}
}
2016
Keywords: 

Distributed Network Computing, Distributed Algorithm, Distributed Decision, Locality 
Seminar: 

43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)

Issue date: 

2016 
Date of publication: 

2016 