Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR19-066 | 3rd May 2019 03:07

A Lower Bound for Sampling Disjoint Sets

RSS-Feed




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



ISSN 1433-8092 | Imprint