I am looking for a reference for the (classical) one way randomised communication complexity of disjointness when the universe can be large. Say Alice and Bob both have sets of size $m$ chosen from a universe of size $U$ and Bob wants to determine if the intersection of their sets is empty or not. I would like prob of error $<1/3$, say.

I can find the standard $\Omega(m)$ bit lower bound and some work on two-way communication complexity, but is there a reference for something tighter for one-way?

EDIT: I should have specified that I am interested in the private randomness (not public coin) model.

  • $\begingroup$ Are the sets chosen at random, or just the communication strategy? $\endgroup$ – mjqxxxx Jan 20 '11 at 17:45
  • $\begingroup$ The randomisation just refers to the fact that Alice and Bob are allowed to use random bits. $\endgroup$ – Raphael Jan 20 '11 at 21:53
  • $\begingroup$ Are you really considering one-way communication (Alice sends a message to Bob who then outputs the answer) or "simultaneous" communication (Alice and Bob each send a message to a referee who announces the answer.) In the former case public and private randomness are the same and so it seems that the answers below (i.e. Mihai's blog) settle the question. $\endgroup$ – Noam Jan 21 '11 at 15:26
  • $\begingroup$ It is the former case of one-way communication as you define it that I am interested in. I am hoping for something tight over the full range of universe sizes. If I understand correctly, Mihai's post gives us an upper bound of $O(m \log{m} + \log{U})$ and we have a lower bound of $\min(\binom{U}{m}, m\log{m})$ which still leaves a gap. $\endgroup$ – Raphael Jan 21 '11 at 16:53
  • $\begingroup$ I mean $\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$ of course. $\endgroup$ – Raphael Jan 21 '11 at 17:28

The answer is $\Theta(m\log m + \log\log |U|)$. In the public coins model, we have (as described above) $\Theta(m\log m)$. As Yuval suggested above, for the upper bound in the private coins model we need only an additive $O(\log n)=O(\log m + \log\log |U|)$ bits (see theorem 3.14 in the K&N book), where $n$ is the length of the encoding of the input ($n=m\log|U|$). For the additional lower bound of $\Omega(\log\log |U|)$ in the private coin model, it is enough to concentrate on the case $m=1$ (as the other items can be fixed to be all different), which is just the equality function on $\log |U|$-bit strings, whose private coin complexity is logarithmic in that (example 3.9 in K&N).

| cite | improve this answer | |
  • $\begingroup$ Thanks, that's perfect however don't we need also to compare it to $\log {\binom{U}{m}}$ which be less than $m\log{m}$ depending on how $U$ relates to $m$. In the extreme case, if $U=m$, Alice doesn't need to say much. $\endgroup$ – Raphael Jan 21 '11 at 18:50
  • $\begingroup$ yes, this is for large $U$ (at least $m^{1+\epsilon}$), otherwise the lower bound mentioned in Mihai's post fails. $\endgroup$ – Noam Jan 21 '11 at 20:01
  • $\begingroup$ this settle the question :-) $\endgroup$ – Marcos Villagra Jan 21 '11 at 23:18
  • $\begingroup$ Btw, I always wanted to ask you, why is the general lower bound of $\log \log |X| \le R(f)$ contained in the K&N book? It would automatically imply things like theorem 3.9. $\endgroup$ – domotorp Jan 22 '11 at 7:12
  • $\begingroup$ Is it known/obvious that $\log{\binom{U}{m}}$ is tight for smaller universe sizes? For example, say $U = m \log{m}$. $\endgroup$ – Raphael Jan 22 '11 at 9:31

For any number of rounds, the lower bound on disjointness is $\Omega(n)$ (cf. The Probabilistic Communication Complexity of Set Intersection. SIAM J. Discrete Math. Volume 5, Issue 4, pp. 545-557 (November 1992)).

For 1-way, Kremer, Nisan, and Ron showed that for any given $f$, $R_\epsilon^1(f)=\Omega(VC(f))$, where $R_\epsilon^1(f)$ is the randomized 1-way communication complexity of $f$ with error $\epsilon$, and $VC(f)$ is the VC-dimension of $f$. Then we have that $VC(DISJ)=n$. But in fact there is a tight lower bound for DISJ, which is $\Omega(n\log n)$ (cf. Mihai Patrascu's blog).

| cite | improve this answer | |
  • $\begingroup$ Mihai Patrascu's blog says that $O(n\log n)$ is achievable even for large universes with the use of a universal hash function. This makes sense if Alice and Bob have a shared source of randomness; but if they have independent sources, doesn't Alice have to tell Bob which hash function she's using? How much space does that take? $\endgroup$ – mjqxxxx Jan 21 '11 at 4:08
  • $\begingroup$ There's a trick that shows that public randomness is the same as private randomness: use a Chernoff bound to show that there exists a polynomial-sized sample space [in the logarithm of the number of possible inputs] which approximates the success probability "well enough" on all inputs; Alice picks one of these points and sends its logarithmic-sized index to Bob. This trick doesn't apply directly in this case (since there are infinitely many inputs), but it can plausibly be adapted somehow. $\endgroup$ – Yuval Filmus Jan 21 '11 at 4:30
  • $\begingroup$ Thanks! I should have specified private randomness in the question. Fixing now. $\endgroup$ – Raphael Jan 21 '11 at 7:55

The private coin (one- and two-way) randomized complexity of ANY function is at least $\log \log |\text{size}|$, so e.g. in your case at least $\log \log {U \choose m}$, which would be $\log \log U$ if $m$ is small, which can give a better lower bound. This result is mentioned in Yao's seminal paper on CC, you can find the proof in my master's thesis, lemma 3.8 and around: http://www.cs.elte.hu/~dom/cikkek/szakdolgozat.pdf

Of course this is just a lower bound, maybe their is a matching upper bound like $m + \log \log U$.

| cite | improve this answer | |

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.