Sampling, flowers and communication

Given a distribution over [n]ⁿsuch that any k coordinates need k/ log^O(1) n bits of communication to sample, we prove that any map that samples this distribution from uniform cells requires locality Δ(log(n/k)/ log log(n/k)). In particular, we show that for any constant δ > 0, there exists ϵ = 2^-Δ(n1-δ)such that Δ(log n/ log log n) non-Adaptive cell probes on uniform cells are required to: Sample a uniformly random permutation on n elements with error 1-ϵ. This provides an exponential improvement on the Δ(log log n) cell probe lower bound by Viola. Sample an n-vector with each element independently drawn from a random n^1-δ-vector, with error 1-ϵ. This provides the first adaptive vs non-Adaptive cell probe separation for sampling. The major technical component in our proof is a new combinatorial theorem about flower with small kernel, i.e. a collection of sets where few elements appear more than once. We show that in a family of n sets, each with size O(log n/ log log n), there must be k = poly(n) sets where at most k/ log^O(1)n elements appear more than once. To show the lower bound on sampling permutation, we also prove a new Δ(k) communication lower bound on sampling uniformly distributed disjoint subsets of [n] of size k, with error 1-2^-Δ(k2/n). This result unifies and subsumes the lower bound for k = Θ(√ n) by Ambainis et al., and the lower bound for k = Θ(n) by Göös and Watso.