Communication complexity of cardinality of set difference

Question

I'm trying to find communication complexity of $f(x, y) = |x \setminus y|$, where x and y are two subsets of the set of integers $\{1, \dots, n\}$. I'm trying to estimate that complexity with $\mathcal{o}(n)$ precision. I came up with an upper bound $D(f) \leq \frac{n \lceil \log n \rceil}{2} + const$ (either Alice can transmit $x$ or its complement $\bar{x}$ or Bob can do the same with $y$ and $\bar{y}$ and the lowest cardinality of a transmitted set is $\frac{n}{2}$, and the set is transmitted by one element), but I think it's inaccurate. Also I tried to find fooling sets, but the lower bound I'm getting using this method is linear $D(f) \geq n + const$. I would be thankful for any ideas that can make my upper and lower bounds closer.

Answer 1

I found the answer. One can transmit a set in form of a bit mask, which takes $n$ bits of information, then the other participant can compute the set difference and transmit back $log(n)$ bits, thus the difference between the lower and the upper bound is $\log n + const$, which is $\mathcal{o}(n)$.