Symmetric Distributions from Shallow Circuits

Abstract

We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let $f:\{0,1{\}}^m\to \{0,1{\}}^n$ be a Boolean function where each output bit depends on at most $d$ input bits. Suppose the output distribution of $f$ evaluated on uniformly random input bits is close in total variation distance to a symmetric distribution $\mathcal{D}$ over $\{0,1{\}}^n$. Then $\mathcal{D}$ must be close to a mixture of the uniform distribution over $n$-bit strings of even Hamming weight, the uniform distribution over $n$-bit strings of odd Hamming weight, and ${\hat{I}}^3$-biased product distributions for ${\hat{I}}^3$ an integer multiple of $2^{-d}$. Moreover, the mixing weights are determined by low-degree, sparse ${\mathbb{F}}_2$-polynomials. This extends the previous classification for generating symmetric distributions that are also uniform over their support.

Version to appear at RANDOM 2026