ECCC-Report TR19-066https://eccc.weizmann.ac.il/report/2019/066Comments and Revisions published for TR19-066en-usTue, 21 Jul 2020 19:16:18 +0300
Revision 2
| A Lower Bound for Sampling Disjoint Sets |
Mika Go?o?s,
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/066#revision2Suppose 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}$.Tue, 21 Jul 2020 19:16:18 +0300https://eccc.weizmann.ac.il/report/2019/066#revision2
Revision 1
| A Lower Bound for Sampling Disjoint Sets |
Mika Göös,
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/066#revision1Suppose 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}$.Tue, 02 Jul 2019 01:26:08 +0300https://eccc.weizmann.ac.il/report/2019/066#revision1
Paper TR19-066
| A Lower Bound for Sampling Disjoint Sets |
Thomas Watson
https://eccc.weizmann.ac.il/report/2019/066Suppose 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}$.Fri, 03 May 2019 03:14:32 +0300https://eccc.weizmann.ac.il/report/2019/066