Kewen Wu, Institute for Advanced Study

Abstract

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let f 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 the all-zero string, (2) point distribution on the all-one string, (3) uniform over all-zero or all-one, (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). Going beyond, we also obtain near-tight classification results for locally sampleable symmetric distribution and propose a conjectured full classification.
Joint works with Daniel Kane and Anthony Ostuni.

See: https://theory.cs.rutgers.edu/theory_seminar