Local Decision and Verification with Bounded-Size Outputs

We are dealing with the design of algorithms using few resources, enabling to decide whether or not any given n-node graph G belongs to some given graph class $\mathcal C$ . Our model borrows from property testing the way the decision is taken, by an unconstrained interpretation function applied to the set of outputs produced by individual queries (instead of an interpretation function limited to the conjunction operator as in local distributed decision). It borrows from local distributed decision the fact that all nodes are involved in the decision (instead of o(n) nodes as in property testing). The unique, but severe restriction we impose to the nodes is a limitation on the amount of information they are enabled to output: every node is bounded to output a constant number of bits. In this paper, we provide separation results between distributed decision and verification classes, and we analyze the size of the certificates enabling to verify distributed languages.