Communication Complexity for Product Distributions

Question

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?

Answer 1

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.

The inner product function doesn't suffer from the same issue. Indeed, it seems that the hardest distribution is the uniform distribution. You can prove a linear lower bound using the discrepancy method – this is standard, and uses a bound on the discrepancy known as Lindsey's lemma.

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)$.