2026-07-21T11:24:03Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:11266 2024-03-06T10:47:50Z ddc:004 open_access

A Lower Bound for Sampling Disjoint Sets Göös, Mika Watson, Thomas Communication complexity set disjointness sampling 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<1, this requires Omega(n) communication even to get within statistical distance 1-beta^n 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 some constant statistical distance epsilon>0 of the uniform distribution over all pairs of disjoint sets of size sqrt{n}. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Mika Göös and Thomas Watson 2019 Is Part Of LIPIcs, Volume 145, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2019) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX-RANDOM.2019.51 urn:nbn:de:0030-drops-112666 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX-RANDOM.2019.51 eng https://creativecommons.org/licenses/by/3.0/legalcode