摘要：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}.
关键词：Communication complexity; set disjointness; sampling
