Locally Sampleable Uniform Symmetric Distributions

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let fλ¶0,1m→0,1n be a Boolean function where each output bit of f depends only on O(1) input bits. Assume the output distribution of f on uniform input bits is close to a uniform distribution D with a symmetric support. We show that D is essentially one of the following six possibilities: (1) point distribution on 0n, (2) point distribution on 1n, (3) uniform over 0n,1n, (4) uniform over strings with even Hamming weights, (5) uniform over strings with odd Hamming weights, and (6) uniform over all strings. This confirms a conjecture of Filmus, Leigh, Riazanov, and Sokolov (RANDOM 2023). This is an extended abstract. The full paper can be found at https://arxiv.org/abs/2411.08183v1. An updated version with a stronger result can be found at https://arxiv.org/abs/2411.08183.