<p>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:</p>
<p><em>Hrubeš, Pavel; Pudlák, Pavel</em>, <a href="http://dx.doi.org/10.1016/j.ipl.2017.11.002" rel="nofollow noreferrer"><strong>A note on monotone real circuits</strong></a>, Inf. Process. Lett. 131, 15-19 (2018). <a href="https://zbmath.org/?q=an:1422.68115" rel="nofollow noreferrer">ZBL1422.68115</a>.</p>
<p><em>Sokolov, Dmitry</em>, <a href="http://dx.doi.org/10.1007/978-3-319-58747-9_26" rel="nofollow noreferrer"><strong>Dag-like communication and its applications</strong></a>,  <a href="https://zbmath.org/?q=an:06763514" rel="nofollow noreferrer">ZBL06763514</a>.</p>

CC BY-SA 4.0
2022-01-21T16:31:31.337Z
2022-01-21T16:31:31.337Z
notautogenerated
<p>I was reading the book &quot;Communication Complexity&quot; 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.</p>
<p>I'll deal just with functions of the form <span class="math-container">$f: \{0,1\}^ \times \{0,1\}^n \to \{0,1\}$</span>.  The definition of a comparison protocol is identical to a classic definition of a communication protocol, except the vertex functions <span class="math-container">$\theta_v$</span> are restricted to a very special form.  Namely, for each vertex <span class="math-container">$v$</span> in a binary tree describing a protocol <span class="math-container">$\mathcal{P}$</span>, the vertex function <span class="math-container">$\theta_v$</span> must be 0 for all inputs less than a given <span class="math-container">$z \in \{0,1\}^n$</span> and 1 for all inputs greater than or equal to <span class="math-container">$z$</span> (where here I am using the usual lexicographical ordering on <span class="math-container">$\{0,1\}^n$</span>.  We can then of course define the communication complexity of a function <span class="math-container">$f$</span> with respect to these comparison protocols and in fact the aforementioned exercise gives a place to start.</p>
<p>Is there any literature on this communication complexity model?  I tried some googling but I didn't have any luck.</p>

<reference-request><communication-complexity>
Comparative communication complexity?
user101010
# Comparative communication complexity?

(Asked by: username_0 on 2022-01-14)

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.

**Tags:** reference-request, communication-complexity

---

## 1 answers

### Answer by username_1 on 2022-01-21. Score: 1

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**](http://dx.doi.org/10.1016/j.ipl.2017.11.002), Inf. Process. Lett. 131, 15-19 (2018). [ZBL1422.68115](https://zbmath.org/?q=an:1422.68115).

*Sokolov, Dmitry*, [**Dag-like communication and its applications**](http://dx.doi.org/10.1007/978-3-319-58747-9_26), [ZBL06763514](https://zbmath.org/?q=an:06763514).


---

