Under the auspices of the Computational Complexity Foundation (CCF)

REPORTS > DETAIL:

### Revision(s):

Revision #1 to TR19-066 | 2nd July 2019 01:26

#### A Lower Bound for Sampling Disjoint Sets

Revision #1
Authors: Mika Göös, Thomas Watson
Accepted on: 2nd July 2019 01:26
Keywords:

Abstract:

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

### Paper:

TR19-066 | 3rd May 2019 03:07

#### A Lower Bound for Sampling Disjoint Sets

TR19-066
Authors: Thomas Watson
Publication: 3rd May 2019 03:14
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}$.