We study the problem of certifying whether a graph is k-colorable with a locally checkable proof (LCP) that is able to hide the k-coloring from the verifier, in the sense that no algorithm can (completely) extract a k-coloring from the certificate. Motivated by the search for promise-free separations of extensions of the LOCAL model in the context of locally checkable labeling (LCL) problems, we also require the LCPs to satisfy what we call the strong soundness property. We focus on the case of 2-coloring and show that strong and hiding LCPs for 2-coloring exist in specific graph classes and require only O (log n)-sized certificates. Furthermore, when the input is promised to be a cycle or contains a node of degree 1, we show the existence of strong and hiding LCPs even in an anonymous network and with constant-size certificates. Despite these upper bounds, we prove that there are no strong and hiding LCPs for 2-coloring in general, regardless of certificate size. Along the way, we give a characterization of the hiding property for the general k-coloring problem that appears to be a key component for future investigations in this context.

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable. The separation results are obtained by approaching communication complexity through an original angle, which may be of an independent interest. The two players are not bounded to compute the value of a binary function, but the combined outputs of the two players are constrained by this value. In particular, we introduce the XOR-Index problem, in which Alice is given a binary vector x ∈ {0,1}ⁿ together with an index i ∈ [n], Bob is given a binary vector y ∈ {0,1}ⁿ together with an index j ∈ [n], and, after a single round of 2-way communication, Alice must output a boolean out_A, and Bob must output a boolean out_B, such that out_A ∧ out_B = x_j⊕ y_i. We show that the communication complexity of XOR-Index is Ω(n) bits.

During the last two decades, a small set of distributed computing models for networks have emerged, among which LOCAL, CONGEST, and Broadcast Congested Clique (BCC) play a prominent role. We consider hybrid models resulting from combining these three models. That is, we analyze the computing power of models allowing to, say, perform a constant number of rounds of CONGEST, then a constant number of rounds of LOCAL, then a constant number of rounds of BCC, possibly repeating this figure a constant number of times. We specifically focus on 2-round models, and we establish the complete picture of the relative powers of these models. That is, for every pair of such models, we determine whether one is (strictly) stronger than the other, or whether the two models are incomparable.