A hierarchy of local decision

Laurent Feuilloley*, Pierre Fraigniaud, Juho Hirvonen

*Corresponding author for this work

Research output: Contribution to journalArticleScientificpeer-review

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