Search Results

We obtain several results on sampling product distributions in a local and randomness-efficient fashion: 1) Let D = (D_1,D_2,…,D_n) be a product distribution where the D_i have constant support and have dyadic probability masses (i.e., of the form a/2^b where a,b are integers). Then D can be sampled in constant time in the bit-probe model (equivalently, in NC⁰) and randomness complexity (h(D)+ε)n, up to an exponentially small statistical error. The dyadic requirement is necessary. 2) Every p-biased distribution can be sampled in constant time in the cell-probe model with randomness complexity h(p)n + √n ⋅ polylog(n), up to a polynomially small statistical distance. 3) We determine the tradeoffs between locality and statistical distance for sampling the 1/4-biased distribution using non-trivial randomness complexity (e.g., 1.99n). For 2 bit probes, essentially no non-trivial approximation is possible; for 3 bit probes, we give a sampler with 1/poly(n) statistical distance and show that this is best possible; finally, 4 bit probes suffice for exponentially small distance. Our constructions rely on pseudorandom distributions that are bounded uniform on average. These distributions are obtained using various tools from low-density parity-check codes, and recent results on succinct and retrieval data structures by Hu, Liang, Yu, Zhang, and Zhou (STOC 2025).