1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Inner product should be hard even for the uniform distribution. You should be able to show it using discrepancy, via Lindzey's lemma. $\endgroup$ – Yuval Filmus May 27 at 7:27
  • $\begingroup$ Not sure what you mean by "intersections". $\endgroup$ – Yuval Filmus May 27 at 7:28
  • $\begingroup$ 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. $\endgroup$ – Cryptonaut May 27 at 10:43
  • 1
    $\begingroup$ You are asking a lot of different questions. I answered some of them. If you like more questions answered, please ask them separately. $\endgroup$ – Yuval Filmus May 27 at 10:45
2
$\begingroup$

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

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Why do we want $X \cdot Y$ to be mostly zero? $\endgroup$ – Cryptonaut May 27 at 10:47
  • $\begingroup$ Essentially because for an OR of variables to be 1, it suffices for one of them to be 1. $\endgroup$ – Yuval Filmus May 27 at 10:48
  • $\begingroup$ So when we try to define hard distributions, the point is that we would like to define input distributions such that the resulting output distribution is close to uniform? Is this the point? $\endgroup$ – Cryptonaut May 27 at 10:54
  • $\begingroup$ 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. $\endgroup$ – Yuval Filmus May 27 at 11:20
  • $\begingroup$ thanks for the clarification! $\endgroup$ – Cryptonaut May 27 at 14:28

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.