A Lower Bound for Sampling Disjoint Sets
Mika Göös, Thomas W. Watson · ACM Transactions on Computation Theory · 2020
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 ⊆ [ n ] and Bob ends up with a set y ⊆ [ n ], such that ( x , y ) is uniformly distributed over all pairs of disjoint sets. We prove that for some constant β 0 of the uniform distribution over all pairs of disjoint sets of size √ n .