A hierarchy of local decision

Laurent Feuilloley*, Pierre Fraigniaud, Juho Hirvonen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

12 Citations (Scopus)
40 Downloads (Pure)

Abstract

We extend the notion of distributed decision in the framework of distributed network computing, inspired by both the polynomial hierarchy for Turing machines and 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 (MST) 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 that certifies nontrivial automorphism with O(log⁡n)-bit certificates. These results are achieved by defining and analyzing a local hierarchy of decision which generalizes the classical notions of proof-labeling schemes and locally checkable proofs.

Original languageEnglish
Pages (from-to)51-67
Number of pages17
JournalTheoretical Computer Science
Volume856
Early online date2020
DOIs
Publication statusPublished - 8 Feb 2021
MoE publication typeA1 Journal article-refereed

Keywords

  • Distributed decision
  • Distributed hierarchy
  • Distributed non-determinism
  • Local certification
  • Local model
  • Proof-labeling scheme

Fingerprint

Dive into the research topics of 'A hierarchy of local decision'. Together they form a unique fingerprint.

Cite this