Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

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

A Lower Bound for Sampling Disjoint Sets

RSS-Feed




Revision #1
Authors: Mika Göös, Thomas Watson
Accepted on: 2nd July 2019 01:26
Downloads: 60
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
Downloads: 321
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