A Hierarchy of Local Decision
Loading...
Access rights
openAccess
publishedVersion
URL
Journal Title
Journal ISSN
Volume Title
A4 Artikkeli konferenssijulkaisussa
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)
Other link related to publication (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)
Other link related to publication (opens in new window)
Date
2016
Department
Major/Subject
Mcode
Degree programme
Language
en
Pages
Series
43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016), Volume 55, pp. 1-15, Leibniz International Proceedings in Informatics (LIPIcs)
Abstract
We extend the notion of distributed decision in the framework of distributed network computing, inspired by recent results on so-called 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 n-node graphs, with just one interaction between the prover and the disprover, while it is known that certifying MST requires(log2 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 (n2) 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 proof-labelling schemes and locally checkable proofs.Description
Keywords
Distributed Algorithm, Distributed Decision, Distributed Network Computing, Locality
Other note
Citation
Feuilloley, L, Fraigniaud, P & Hirvonen, J 2016, A Hierarchy of Local Decision . in Y R Ioannis Chatzigiannakis Michael Mitzenmacher & D Sangiorgi (eds), 43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016) . vol. 55, 118, Leibniz International Proceedings in Informatics (LIPIcs), Schloss Dagstuhl - Leibniz-Zentrum für Informatik, Dagstuhl, Germany, pp. 1-15, International Colloquium on Automata, Languages and Programming, Rome, Italy, 12/07/2016 . https://doi.org/10.4230/LIPIcs.ICALP.2016.118