Using a probability distribution in the fooling set technique for communication complexity

Question

I'm reading through the communication complexity book of Kushilevitz and Nisan, and in the section about fooling sets I encountered this proposition:

Let $\mu$ be a probability distribution of $X\times Y$. If any $f$-monochromatic rectange $R$ has measure $\mu(R) \leq \delta$, then $D(f) \geq \log_2 1/\delta$. [Prop. 1.24]

I understand the idea of a fooling set (find a set which takes the same function value everywhere, but mixing and matching $x$ and $y$ coordinates will change the function value). I understand that $\mu$ maps $X\times Y$ to $\mathbb{R}$, and that $\mu(X\times Y) = 1$. But I don't understand why we should be allowed to use a probability distribution at all. There's no randomness here, and even if their likelihoods of being chosen were not uniform, each pair $(x,y)$ should in theory be possible, and we need to take this into consideration because communication complexity deals with the worst-case.

I'm obviously missing something. Any help here would be appreciated.

(Also, the use of any in the proposition is ambiguous. I assume that it means "for all", but it could also possibly mean "there exists"...)

Answer 1

It is true that there is "no randomness" in the sense that the protocol is not randomized and is supposed to work on all inputs. However, that does not mean that we are not allowed to use probability distributions in the analysis of the algorithm.

This theorem says that when you wish to prove a lower bound, then for the purpose of the analysis, you can take whatever distribution $\mu$ you like, and the communication complexity would be at least $\log(1/\delta)$, where $\delta$ is the largest probability of a monochromatic rectangle.

If you do not like thinking about it in terms of probability, you can also think about it as a counting argument. Suppose you could prove that every monochromatic rectangle contains at most $t$ pairs. Then, this would imply that the communication complexity must be at least $\log\left(\frac{|X \times Y|}{t}\right)$ by simple counting.

Now, the foregoing argument is exactly equivalent to applying the theorem you stated with $\mu$ being the uniform distribution and $\delta$ being $\frac{t}{|X \times Y|}$. The theorem generalizes this argument to work with probability distributions other than the uniform.

In the case the distribution is not uniform, this is equivalent to augmenting the counting argument with weights. Suppose you assign each pair some weight such that

• The total weight of $X \times Y$ is $W$.
• Every monochromatic rectangle has weight at most $w$.

Then, clearly the communication complexity must be at least $\log(W/w)$ (since there must be at least $W/w$ monochromatic rectangles). The theorem you stated is just a different way to look at this argument.