We obtain several results on sampling product distributions in a local and randomness-efficient fashion:

- Let $D=(D_1,D_2,\ldots,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$^0$) and randomness complexity $(h(D)+\varepsilon)n$, up to an exponentially small statistical error. The dyadic requirement is necessary.

- Every $p$-biased distribution can be sampled in constant time in the cell-probe model with randomness complexity $h(p)n + \sqrt{n} \cdot \rm{polylog}(n)$, up to a polynomially small statistical distance.

- 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/\rm{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).

Major revisions, including title, introduction and some proofs

We give versions of Shannon's coding theorem where the decoder runs in constant time:

- Let $D=(D_1,D_2,\ldots,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$^0$) and randomness complexity $(h(D)+\varepsilon)n$, up to an exponentially small statistical error. The dyadic requirement is necessary.

- Every $p$-biased distribution can be sampled in constant time in the cell-probe model with randomness complexity $h(p)n + \sqrt{n} \cdot \rm{polylog}(n)$, up to a polynomially small statistical distance.

- 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/\rm{poly}(n)$ statistical distance and show that this is best possible; finally, 4 bit probes suffice for exponentially small distance.