A Hierarchy of Local Decision

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen

Tutkimustuotos: Artikkeli kirjassa/konferenssijulkaisussaConference contributionScientificvertaisarvioitu

20 Sitaatiot (Scopus)
46 Lataukset (Pure)


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.
Otsikko43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
ToimittajatYuval Rabani Ioannis Chatzigiannakis Michael Mitzenmacher, Davide Sangiorgi
JulkaisupaikkaDagstuhl, Germany
KustantajaSchloss Dagstuhl-Leibniz-Zentrum für Informatik
ISBN (painettu)978-3-95977-013-2
DOI - pysyväislinkit
TilaJulkaistu - 2016
OKM-julkaisutyyppiA4 Artikkeli konferenssijulkaisuussa
TapahtumaInternational Colloquium on Automata, Languages and Programming - Rome, Italia
Kesto: 12 heinäk. 201615 heinäk. 2016
Konferenssinumero: 43


NimiLeibniz International Proceedings in Informatics (LIPIcs)
KustantajaSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik


ConferenceInternational Colloquium on Automata, Languages and Programming


Sukella tutkimusaiheisiin 'A Hierarchy of Local Decision'. Ne muodostavat yhdessä ainutlaatuisen sormenjäljen.

Siteeraa tätä