One way randomised communication complexity of disjointness
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&amp;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&amp;N).