fixed typo
Source Link
domotorp
  • 13.5k
  • 34
  • 91

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 mebe 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.

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 me 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.

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.

Source Link

Comparative communication complexity?

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 me 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.