# Communication Complexity for Product Distributions

In general for the (two-party) set disjointness problem for inputs of length n, we know that the parties need to communicate $$\Omega(n)$$. Surprisingly, today I discovered (if I understood correctly) that this is not true for product distributions, i.e. when Alice's and Bob's inputs are chosen independently from arbitrary distributions! In this paper, for example, they provide an upper bound with communication complexity $$\mathcal{O}(\sqrt{n}\log(1/\epsilon))$$, where $$\epsilon$$ is some error term not relevant for the question here. Now I am curious about whether gaps exist for other well known communication complexity problems.

Question: What other well-known problems exhibit a gap between the communication complexities when one considers arbitrary input distributions and product distributions. Are there similar results for inner products or intersections?

• Inner product should be hard even for the uniform distribution. You should be able to show it using discrepancy, via Lindzey's lemma. Commented May 27, 2020 at 7:27
• Not sure what you mean by "intersections". Commented May 27, 2020 at 7:28
• By intersection I meant that Alice and Bob hold sets of elements $A = \{a_1, \dots, a_n\}$ and $B = \{b_1, \dots, b_n\}$ (from some space) and would like to compute the intersection $C = \{ c \in A \mid c \in B \}$. I have seen several works mentioning this problem with the statement that a linear communication lower bound follows from the lower bound for set disjointness. So given that the lower bound for set disjointness does not hold for product distributions, I was wondering whether this also is true for the intersection problem. Commented May 27, 2020 at 10:43
• You are asking a lot of different questions. I answered some of them. If you like more questions answered, please ask them separately. Commented May 27, 2020 at 10:45

Set disjointness is easier for product distributions since the hard distribution for set disjointness is very far from being a product distribution. What do we require from a hard distribution $$(X,Y)$$ for inner product? We want each of $$X,Y$$ separately to be quite random, and we want $$X\cdot Y$$ to be mostly zero, say $$X \cdot Y$$ contains at most a single $$1$$. This cannot be accomplished by a product distribution. While you can get the $$X \cdot Y$$ property, this implies that each of the two inputs will be very biased. Conversely, if the inputs $$X,Y$$ are quite random, then $$X \cdot Y$$ will have many $$1$$s.
Sherstov came up with an optimal gap example in his paper Communication complexity under product and nonproduct distributions. His function is a random function, chosen so that there are no large monochromatic $$1$$-rectangles. The end result is a function whose randomized communication complexity is $$\Omega(n)$$, but for any product distribution, the randomized communication complexity is $$O(1)$$.
• Why do we want $X \cdot Y$ to be mostly zero? Commented May 27, 2020 at 10:47
• That would certainly be helpful. But the idea is different: if you $X \cdot Y$ has many ones on average, then the distribution is very easy, since the answer is almost always 1. You can just output 1, and your error would be very small. Commented May 27, 2020 at 11:20