Locally Sampleable Uniform Symmetric Distributions

Abstract

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f:\{0,1{\}}^m\to \{0,1{\}}^n$ 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 $0^n$, (2) point distribution on $1^n$, (3) uniform over $\{0^n,1^n\}$, (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 version improves the main result by removing dependence on d from the final distance bound