A Hierarchy of Local Decision

Laurent Feuilloley, Pierre Fraigniaud, Juho Hirvonen

Research output: Chapter in Book/Report/Conference proceedingConference contributionScientificpeer-review

20 Citations (Scopus)
43 Downloads (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.
Original languageEnglish
Title of host publication43rd International Colloquium on Automata, Languages, and Programming (ICALP 2016)
EditorsYuval Rabani Ioannis Chatzigiannakis Michael Mitzenmacher, Davide Sangiorgi
Place of PublicationDagstuhl, Germany
PublisherSchloss Dagstuhl-Leibniz-Zentrum für Informatik
ISBN (Print)978-3-95977-013-2
Publication statusPublished - 2016
MoE publication typeA4 Article in a conference publication
EventInternational Colloquium on Automata, Languages and Programming - Rome, Italy
Duration: 12 Jul 201615 Jul 2016
Conference number: 43

Publication series

NameLeibniz International Proceedings in Informatics (LIPIcs)
PublisherSchloss Dagstuhl--Leibniz-Zentrum fuer Informatik


ConferenceInternational Colloquium on Automata, Languages and Programming
Abbreviated titleICALP


  • Distributed Algorithm
  • Distributed Decision
  • Distributed Network Computing
  • Locality


Dive into the research topics of 'A Hierarchy of Local Decision'. Together they form a unique fingerprint.

Cite this