A Hierarchy of Local Decision

Laurent Feuilloley, Juho Hirvonen, Pierre Fraigniaud.

Theoretical Computer Science. 2021.
doi:10.1016/j.tcs.2020.12.017

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 $\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 that certifies 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-labeling schemes and locally checkable proofs.

This paper has been presented in the conference ICALP 2016. The webpage of the conference version is here.

The main differences between the (full) version of the conference and the journal version are the following. As suggested by a reviwer the computability assumption we had on the language has been removed to get a cleaner setting. Following another reviewers' suggestion we added a detailed example of some decision in the hierarchy. In addition, we updated and developped the related work. Various more modest changes have also been made.

I gave a talk about this paper at ICALP, at the final meeting of the project ANR Displexity, and at a winter school ( EJCIM 17).

I presented the poster at the Workshop on Local Algorithms (WoLA, in Boston, mid-october 2016) and at the same winter school.

A paper of similar flavour, What Can Be Verified Locally?, written by Alkida Balliu, Gianlorenzo D'Angelo, Pierre Fraigniaud and Dennis Olivetti was published at STACS 2017. The difference is that in our work, the certificates can depend on the IDs and the challenge is to cope with the $O(\log n)$ size limit, whereas in their paper, there is no size limit but the certificates cannot depend on the IDs. The resulting complexity landscape is completely different.

Another work about a similar hierarchy (among other things) is Towards a complexity theory for the congested clique, written by Janne H. Korhonen and Jukka Suomela which appeared at SPAA 2018. There, the underlying model is the congested clique instead of the local model.

In a paper with Juho Hirvonen, Local verification of global proofs, we proved that the main open question of this paper (about the collapse of the hierarchy) had deep connexions to a well-known open problem in communication complexity.