# One way randomised communication complexity of disjointness

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.

• Are the sets chosen at random, or just the communication strategy? – mjqxxxx Jan 20 '11 at 17:45
• The randomisation just refers to the fact that Alice and Bob are allowed to use random bits. – Raphael Jan 20 '11 at 21:53
• 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. – Noam Jan 21 '11 at 15:26
• 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. – Raphael Jan 21 '11 at 16:53
• I mean $\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$ of course. – 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).

• 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. – Raphael Jan 21 '11 at 18:50
• yes, this is for large $U$ (at least $m^{1+\epsilon}$), otherwise the lower bound mentioned in Mihai's post fails. – Noam Jan 21 '11 at 20:01
• this settle the question :-) – Marcos Villagra Jan 21 '11 at 23:18
• 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. – domotorp Jan 22 '11 at 7:12
• Is it known/obvious that $\log{\binom{U}{m}}$ is tight for smaller universe sizes? For example, say $U = m \log{m}$. – 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).

• 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? – mjqxxxx Jan 21 '11 at 4:08
• 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. – Yuval Filmus Jan 21 '11 at 4:30
• Thanks! I should have specified private randomness in the question. Fixing now. – 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$$.