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.

  • $\begingroup$ 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. $\endgroup$ Jan 11 at 14:25
  • $\begingroup$ @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. $\endgroup$
    – user101010
    Jan 12 at 2:55
  • $\begingroup$ 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). $\endgroup$
    – user101010
    Jan 12 at 3:01

Your Answer

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

Browse other questions tagged or ask your own question.