8
$\begingroup$

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.

Improve this question
$\endgroup$
6
  • $\begingroup$ Are the sets chosen at random, or just the communication strategy? $\endgroup$
    – mjqxxxx
    Commented Jan 20, 2011 at 17:45
  • $\begingroup$ The randomisation just refers to the fact that Alice and Bob are allowed to use random bits. $\endgroup$
    – Simd
    Commented Jan 20, 2011 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
    Commented Jan 21, 2011 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$
    – Simd
    Commented Jan 21, 2011 at 16:53
  • $\begingroup$ I mean $\Omega(\min(\log{\binom{U}{m}}, m\log{m}))$ of course. $\endgroup$
    – Simd
    Commented Jan 21, 2011 at 17:28

3 Answers 3

Reset to default
9
$\begingroup$

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

Improve this answer
$\endgroup$
5
  • $\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$
    – Simd
    Commented Jan 21, 2011 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
    Commented Jan 21, 2011 at 20:01
  • $\begingroup$ this settle the question :-) $\endgroup$
    – Marcos Villagra
    Commented Jan 21, 2011 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
    Commented Jan 22, 2011 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$
    – Simd
    Commented Jan 22, 2011 at 9:31
5
$\begingroup$

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

Improve this answer
$\endgroup$
3
  • $\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
    Commented Jan 21, 2011 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
    Commented Jan 21, 2011 at 4:30
  • $\begingroup$ Thanks! I should have specified private randomness in the question. Fixing now. $\endgroup$
    – Simd
    Commented Jan 21, 2011 at 7:55
3
$\begingroup$

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

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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