Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. We prove that for some constant $\beta 0$ of the uniform distribution over all pairs of disjoint sets of size $\sqrt{n}$.

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. We prove that for some constant $\beta0$ of the uniform distribution over all pairs of disjoint sets of size $\sqrt{n}$.

Suppose Alice and Bob each start with private randomness and no other input, and they wish to engage in a protocol in which Alice ends up with a set $x\subseteq[n]$ and Bob ends up with a set $y\subseteq[n]$, such that $(x,y)$ is uniformly distributed over all pairs of disjoint sets. We prove that for some constant $\varepsilon>0$, this requires $\Omega(n)$ communication even to get within statistical distance $\varepsilon$ of the target distribution. Previously, Ambainis, Schulman, Ta-Shma, Vazirani, and Wigderson (FOCS 1998) proved that $\Omega(\sqrt{n})$ communication is required to get within $\varepsilon$ of the uniform distribution over all pairs of disjoint sets of size $\sqrt{n}$.