<p>For any number of rounds, the lower bound on disjointness is $\Omega(n)$ (cf. <a href="http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&amp;id=SJDMEC000005000004000545000001&amp;idtype=cvips&amp;gifs=yes&amp;ref=no" rel="nofollow">The Probabilistic Communication Complexity of Set Intersection. SIAM J. Discrete Math. Volume 5, Issue 4, pp. 545-557 (November 1992)</a>).</p>

<p>For 1-way, <a href="http://www.springerlink.com/content/w5pccfda9jbhpgdj/" rel="nofollow">Kremer, Nisan, and Ron</a> 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 <a href="http://en.wikipedia.org/wiki/VC_dimension" rel="nofollow">VC-dimension</a> 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. <a href="http://infoweekly.blogspot.com/2009/04/cc4-one-way-communication-and-puzzle.html" rel="nofollow">Mihai Patrascu's blog</a>).</p>

CC BY-SA 2.5
2011-01-21T04:08:18.100Z
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
CC BY-SA 2.5
2011-01-21T04:30:48.560Z
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
CC BY-SA 2.5
2011-01-21T07:55:22.643Z
Thanks! I should have specified private randomness in the question. Fixing now.
Simd
CC BY-SA 2.5
2011-01-21T00:06:19.200Z
2011-01-21T01:05:33.517Z
2011-01-21T01:05:33.517Z
Marcos Villagra
<p>The private coin (one- and two-way) randomized complexity of ANY function is at least <span class="math-container">$\log \log |\text{size}|$</span>, so e.g. in your case at least <span class="math-container">$\log \log {U \choose m}$</span>, which would be <span class="math-container">$\log \log U$</span> if <span class="math-container">$m$</span> 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:
<a href="http://www.cs.elte.hu/~dom/cikkek/szakdolgozat.pdf" rel="nofollow noreferrer">http://www.cs.elte.hu/~dom/cikkek/szakdolgozat.pdf</a></p>

<p>Of course this is just a lower bound, maybe their is a matching upper bound like <span class="math-container">$m + \log \log U$</span>.</p>

CC BY-SA 4.0
2011-01-21T17:09:36.393Z
2019-01-24T20:22:38.560Z
2019-01-24T20:22:38.560Z
domotorp
<p>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 <a href="http://books.google.com/books?id=9A_9Jcs1ZJQC&amp;printsec=frontcover&amp;dq=kushilevitz+nisan&amp;source=bl&amp;ots=XmY8oc3nFX&amp;sig=BIslnB-7N95ybsDfUxJDhD1EVq4&amp;hl=en&amp;ei=hsI5TcrHL4OKhQe99Y3MCg&amp;sa=X&amp;oi=book_result&amp;ct=result&amp;resnum=3&amp;ved=0CCgQ6AEwAg#v=onepage&amp;q&amp;f=false">K&amp;N book</a>), 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&amp;N).</p>

CC BY-SA 2.5
2011-01-21T18:50:11.490Z
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.
Simd
CC BY-SA 2.5
2011-01-21T20:01:20.743Z
yes, this is for large $U$ (at least $m^{1+\epsilon}$), otherwise the lower bound mentioned in Mihai's post fails.
Noam
CC BY-SA 2.5
2011-01-21T23:18:14.983Z
this settle the question :-)
Marcos Villagra
CC BY-SA 2.5
2011-01-22T07:12:53.263Z
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
CC BY-SA 2.5
2011-01-22T09:31:24.270Z
Is it known/obvious that $\log{\binom{U}{m}}$ is tight for smaller universe sizes? For example, say $U = m \log{m}$.
Simd
CC BY-SA 2.5
2011-01-21T17:39:24.343Z
2011-01-21T17:39:24.343Z
Noam
<p>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 $&lt;1/3$, say.</p>

<p>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?  </p>

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

CC BY-SA 2.5
2011-01-20T17:45:59.780Z
Are the sets chosen at random, or just the communication strategy?
mjqxxxx
CC BY-SA 2.5
2011-01-20T21:53:54.537Z
The randomisation just refers to the fact that Alice and Bob are allowed to use random bits.
Simd
CC BY-SA 2.5
2011-01-21T15:26:27.083Z
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
CC BY-SA 2.5
2011-01-21T16:53:12.487Z
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.
Simd
CC BY-SA 2.5
2011-01-21T17:28:22.677Z
I mean $\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$ of course.
Simd
CC BY-SA 2.5
2011-01-22T12:29:48.457Z
Erratum: There are typo/thinkos in my comments above. Look at Noam's reply for the correct answer.
Simd
<cc.complexity-theory><reference-request><lower-bounds><communication-complexity>
One way randomised communication complexity of disjointness
Simd
# One way randomised communication complexity of disjointness

(Asked by: username_0 on 2011-01-20)

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.

**Tags:** cc.complexity-theory, reference-request, lower-bounds, communication-complexity
> **Comments:**
> **username_1**: Are the sets chosen at random, or just the communication strategy?  
> **username_0**: The randomisation just refers to the fact that Alice and Bob are allowed to use random bits.  
> **username_2**: 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.  
> **username_0**: 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.  
> **username_0**: I mean $\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$ of course.  
> **username_0**: Erratum: There are typo/thinkos in my comments above. Look at Noam's reply for the correct answer.  

---

## 3 answers

### Answer by username_2 on 2011-01-21. Score: 9 | Accepted answer

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](http://books.google.com/books?id=9A_9Jcs1ZJQC&printsec=frontcover&dq=kushilevitz+nisan&source=bl&ots=XmY8oc3nFX&sig=BIslnB-7N95ybsDfUxJDhD1EVq4&hl=en&ei=hsI5TcrHL4OKhQe99Y3MCg&sa=X&oi=book_result&ct=result&resnum=3&ved=0CCgQ6AEwAg#v=onepage&q&f=false)), 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).

> **Comments:**
> **username_0**: 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.  
> **username_2**: yes, this is for large $U$ (at least $m^{1+\epsilon}$), otherwise the lower bound mentioned in Mihai's post fails.  
> **username_3**: this settle the question :-)  
> **username_5**: 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.  
> **username_0**: Is it known/obvious that $\log{\binom{U}{m}}$ is tight for smaller universe sizes? For example, say $U = m \log{m}$.  

---

### Answer by username_3 on 2011-01-21. Score: 5

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)](http://scitation.aip.org/getabs/servlet/GetabsServlet?prog=normal&id=SJDMEC000005000004000545000001&idtype=cvips&gifs=yes&ref=no)).

For 1-way, [Kremer, Nisan, and Ron](http://www.springerlink.com/content/w5pccfda9jbhpgdj/) 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](http://en.wikipedia.org/wiki/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](http://infoweekly.blogspot.com/2009/04/cc4-one-way-communication-and-puzzle.html)).

> **Comments:**
> **username_1**: 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?  
> **username_4**: 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.  
> **username_0**: Thanks! I should have specified private randomness in the question. Fixing now.  

---

### Answer by username_5 on 2011-01-21. Score: 3

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


---

