<p>This question is certainly below research level, however I figured I would get the best answer here.  I just started learning about computational complexity (from Arora and Barak) and I have a question about the presumably most basic lower bound.  Let <span class="math-container">$f: \{0,1\}^{2n} \to \{0,1\}$</span> be a boolean function and denote by <span class="math-container">$C(f)$</span> the communication complexity of <span class="math-container">$f$</span>.  From poking around, it looks to me like there are a few different definitions/models of <span class="math-container">$C(f)$</span> so just to be totally concrete I'll repeat the one used by Arora and Barak (which is the one I wish to consider).  Alice and Bob agree on a fixed protocol <span class="math-container">$P$</span> which consists of the functions <span class="math-container">$P_1,...,P_t : \{0,1\}^* \to \{0,1\}^*$</span> and we say <span class="math-container">$P$</span> computes <span class="math-container">$f$</span> if the sequence for all inputs <span class="math-container">$(x,y) \in \{0,1\}^{2n}$</span> the sequence <span class="math-container">$p_1 = P_1(x),p_2 = P_2(y, p_1), p_3 = P_3(x,p_1,p_2), p_4 = P_4(y, p_1,p_2,p_3),..., p_t$</span> ends with <span class="math-container">$p_t = f(x,y)$</span>.  The cost of <span class="math-container">$P$</span> is the largest value of <span class="math-container">$|p_1| + \cdots + |p_t|$</span> over all inputs.  Then the communication complexity of <span class="math-container">$f$</span>, <span class="math-container">$C(f)$</span>, is the minimum cost over all protocols that compute <span class="math-container">$f$</span>.</p>
<p>The name of the game in computational complexity theory is to obtain lower bounds for <span class="math-container">$C(f)$</span>.  Let <span class="math-container">$M(f)$</span> be the <span class="math-container">$2^n \times 2^n$</span>-matrix formed by the values of <span class="math-container">$f$</span>.  Then <span class="math-container">$\chi(f)$</span> is the minimum number of rectangles needed to tile <span class="math-container">$M(f)$</span> with monochromatic rectangles (i.e., every value inside of a rectangle is the same).  My confusion is with the proof that <span class="math-container">$C(f) \geq \log \chi(f)$</span>.</p>
<p>The proof relies on the concept of considering the computation histories of a protocol <span class="math-container">$P$</span>.  Given a protocol <span class="math-container">$P$</span> and input <span class="math-container">$(x,y)$</span> the history <span class="math-container">$\mathcal{H}_{(x,y)}$</span> is the bit <span class="math-container">$p_1 p_2 \cdots p_t$</span> for the input <span class="math-container">$(x,y)$</span>.  Note that it is perfectly possible to have <span class="math-container">$\mathcal{H}_{(x,y)} = \mathcal{H}_{(x',y')}$</span> but not have the <span class="math-container">$p_i$</span> for input <span class="math-container">$(x,y)$</span> all equal to the <span class="math-container">$p_i$</span> for <span class="math-container">$(x',y')$</span>.  The issue being that in <span class="math-container">$\mathcal{H}_{(x,y)}$</span>, I am not keeping track where the breaks in the communication occur.</p>
<p>Now the idea of the proof that <span class="math-container">$C(f) \geq \log \chi(f)$</span> is that we are to take some protocol <span class="math-container">$P$</span> that computes <span class="math-container">$f$</span> and note that there are at most <span class="math-container">$2^{cost(P)}$</span> computational histories for <span class="math-container">$P$</span> and if we label each square of <span class="math-container">$M(f)$</span> with its computational history, we are supposed to obtain a monochromatic tiling of <span class="math-container">$M(f)$</span> where the tiles <span class="math-container">$R_\mathcal{H}$</span> are then all entries that are labeled by a given possible computation history <span class="math-container">$\mathcal{H}$</span>.</p>
<p>It is evident that the <span class="math-container">$R_\mathcal{H}$</span> are monochromatic (since the last bit of a computation history is the value of <span class="math-container">$f$</span> on that entry), however it is not clear to me why the <span class="math-container">$R_\mathcal{H}$</span> need to be rectangles.  Why is this the case?</p>
<p>If each <span class="math-container">$P_i$</span> just output a single bit (as is assumed in the book), then I understand why this is (for example then we don't have the issue I mentioned in the third paragraph), since then a square being in <span class="math-container">$R_\mathcal{H}$</span> is equivalent to having the odd place bits as Alice's communications and the even bits as Bob's (and then by induction on the number of communication steps we see the <span class="math-container">$R_\mathcal{H}$</span> are rectangles.</p>
<p>Thanks for any pointers.</p>

CC BY-SA 4.0
2022-01-11T14:25:06.187Z
Are you sure you are using the right concept of rectangle, a Cartesian product of sets of x and y indices? You use "square" at one point which makes me think you are thinking of geometric rectangles, which these are not.
András Salamon
CC BY-SA 4.0
2022-01-12T02:55:15.987Z
@AndrásSalamon Maybe square was not the right word - but I used square to just mean an entry of the matrix $M(f)$.  I have certainly made the mistake you just mentioned, but I think the above discussion is free of that error.
user101010
CC BY-SA 4.0
2022-01-12T03:01:26.687Z
I should mention that in Kushilevitz and Nisan they present this 2-player deterministic model in a slightly different way in which the proof is very clean.  It is not clear to me how the complexity measure from their model converts to the complexity measure in the model I discussed (which I personally prefer).
user101010
<communication-complexity>
Subtle part of seeing $C(F) \geq \chi(f)$
user101010
# Subtle part of seeing $C(F) \geq \chi(f)$

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

This question is certainly below research level, however I figured I would get the best answer here. I just started learning about computational complexity (from Arora and Barak) and I have a question about the presumably most basic lower bound. Let $f: \{0,1\}^{2n} \to \{0,1\}$ be a boolean function and denote by $C(f)$ the communication complexity of $f$. From poking around, it looks to me like there are a few different definitions/models of $C(f)$ so just to be totally concrete I'll repeat the one used by Arora and Barak (which is the one I wish to consider). Alice and Bob agree on a fixed protocol $P$ which consists of the functions $P\_1,...,P\_t : \{0,1\}^\* \to \{0,1\}^\*$ and we say $P$ computes $f$ if the sequence for all inputs $(x,y) \in \{0,1\}^{2n}$ the sequence $p\_1 = P\_1(x),p\_2 = P\_2(y, p\_1), p\_3 = P\_3(x,p\_1,p\_2), p\_4 = P\_4(y, p\_1,p\_2,p\_3),..., p\_t$ ends with $p\_t = f(x,y)$. The cost of $P$ is the largest value of $|p\_1| + \cdots + |p\_t|$ over all inputs. Then the communication complexity of $f$, $C(f)$, is the minimum cost over all protocols that compute $f$.

The name of the game in computational complexity theory is to obtain lower bounds for $C(f)$. Let $M(f)$ be the $2^n \times 2^n$-matrix formed by the values of $f$. Then $\chi(f)$ is the minimum number of rectangles needed to tile $M(f)$ with monochromatic rectangles (i.e., every value inside of a rectangle is the same). My confusion is with the proof that $C(f) \geq \log \chi(f)$.

The proof relies on the concept of considering the computation histories of a protocol $P$. Given a protocol $P$ and input $(x,y)$ the history $\mathcal{H}\_{(x,y)}$ is the bit $p\_1 p\_2 \cdots p\_t$ for the input $(x,y)$. Note that it is perfectly possible to have $\mathcal{H}\_{(x,y)} = \mathcal{H}\_{(x',y')}$ but not have the $p\_i$ for input $(x,y)$ all equal to the $p\_i$ for $(x',y')$. The issue being that in $\mathcal{H}\_{(x,y)}$, I am not keeping track where the breaks in the communication occur.

Now the idea of the proof that $C(f) \geq \log \chi(f)$ is that we are to take some protocol $P$ that computes $f$ and note that there are at most $2^{cost(P)}$ computational histories for $P$ and if we label each square of $M(f)$ with its computational history, we are supposed to obtain a monochromatic tiling of $M(f)$ where the tiles $R\_\mathcal{H}$ are then all entries that are labeled by a given possible computation history $\mathcal{H}$.

It is evident that the $R\_\mathcal{H}$ are monochromatic (since the last bit of a computation history is the value of $f$ on that entry), however it is not clear to me why the $R\_\mathcal{H}$ need to be rectangles. Why is this the case?

If each $P\_i$ just output a single bit (as is assumed in the book), then I understand why this is (for example then we don't have the issue I mentioned in the third paragraph), since then a square being in $R\_\mathcal{H}$ is equivalent to having the odd place bits as Alice's communications and the even bits as Bob's (and then by induction on the number of communication steps we see the $R\_\mathcal{H}$ are rectangles.

Thanks for any pointers.

**Tags:** communication-complexity
> **Comments:**
> **username_1**: Are you sure you are using the right concept of rectangle, a Cartesian product of sets of x and y indices? You use "square" at one point which makes me think you are thinking of geometric rectangles, which these are not.  
> **username_0**: @AndrásSalamon Maybe square was not the right word - but I used square to just mean an entry of the matrix $M(f)$.  I have certainly made the mistake you just mentioned, but I think the above discussion is free of that error.  
> **username_0**: I should mention that in Kushilevitz and Nisan they present this 2-player deterministic model in a slightly different way in which the proof is very clean.  It is not clear to me how the complexity measure from their model converts to the complexity measure in the model I discussed (which I personally prefer).  

---

## 0 answers

