I was reading the book "Communication Complexity" by Kuschilevitz and Nisan and in Exercise 1.18 they introduce a variant of the normal vanilla 2-person deterministic communication complexity protocol which they call a comparative protocol.

I'll deal just with functions of the form $f: \{0,1\}^ \times \{0,1\}^n \to \{0,1\}$. The definition of a comparison protocol is identical to a classic definition of a communication protocol, except the vertex functions $\theta_v$ are restricted to a very special form. Namely, for each vertex $v$ in a binary tree describing a protocol $\mathcal{P}$, the vertex function $\theta_v$ must be 0 for all inputs less than a given $z \in \{0,1\}^n$ and 1 for all inputs greater than or equal to $z$ (where here I am using the usual lexicographical ordering on $\{0,1\}^n$. We can then of course define the communication complexity of a function $f$ with respect to these comparison protocols and in fact the aforementioned exercise gives a place to start.

Is there any literature on this communication complexity model? I tried some googling but I didn't have any luck.


Not exactly what you are asking but the DAG-like version of this model has been studied, here are some recent references in case it helps:

Hrubeš, Pavel; Pudlák, Pavel, A note on monotone real circuits, Inf. Process. Lett. 131, 15-19 (2018). ZBL1422.68115.

Sokolov, Dmitry, Dag-like communication and its applications, ZBL06763514.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.