Symmetric Distributions from Shallow Circuits

Another cool recent work on sampling: Kane, Ostuni, and Wu have recently posted a neat characterization of the symmetric distributions that can be approximately sampled in NC^0: A symmetric distribution can be sampled iff it’s a combo of i.i.d. with dyadic bias a/2^i, and uniform with sum = b mod 2, for various a,b.

This result is related to a recent work that Horacsek, Lee, Shinkar, Zhou and myself have recently posted. We show that any product distribution with dyadic weights can be sampled in NC^0 using a number of input bits that is close to the entropy of the distribution. This can be thought of as a local version of Shannon’s coding theorem (specifically, the decoding of the source can be done locally).

There is no shortage of questions, can we generalize these results to other models and distributions?

Returning to the first paper I mentioned, a couple of comments on the write-up (in case you read it):

1. Their opening sentence makes me happy that I wrote myth-creation-the-switching-lemma
2. For my perspective on sampling and especially the relationship with some previous works see this.