Locally Sampleable Uniform Symmetric Distributions
Kewen Wu (UC Berkeley)
Monday, January 27th 2025, 2-3pm
Abstract:
We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let f:{0,1}^m -> {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).
Joint work with Daniel M. Kane and Anthony Ostuni.