# A Hierarchy of Local Decision

1 GANG - Networks, Graphs and Algorithms
IRIF - Institut de Recherche en Informatique Fondamentale, Inria de Paris
Abstract : We extend the notion of \emph{distributed decision} in the framework of distributed network computing, inspired by recent results on so-called \emph{distributed graph automata}. We show that, by using distributed decision mechanisms based on the interaction between a \emph{prover} and a \emph{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 $\Omega(\log^2n)$-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 $\Omega(n^2)$ 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 \emph{local hierarchy} of decision which generalizes the classical notions of \emph{proof-labelling schemes} and \emph{locally checkable proofs}.
Type de document :
Communication dans un congrès
43rd International Colloquium on Automata, Languages, and Programming (ICALP) , 2016, Roma, Italy. 2016
Domaine :

https://hal.inria.fr/hal-01423644
Contributeur : Pierre Fraigniaud <>
Soumis le : vendredi 30 décembre 2016 - 18:15:42
Dernière modification le : jeudi 11 janvier 2018 - 06:28:03

### Identifiants

• HAL Id : hal-01423644, version 1

### Citation

Pierre Fraigniaud, Laurent Feuilloley, Juho Hirvonen. A Hierarchy of Local Decision. 43rd International Colloquium on Automata, Languages, and Programming (ICALP) , 2016, Roma, Italy. 2016. 〈hal-01423644〉

### Métriques

Consultations de la notice