Seminar Details
Locally Sampleable (Uniform) Symmetric Distributions
- Start Date: September 17, 2025
- Event Start Time: 11:00 AM
- Event End Time: 12:00 PM
- Seminar Series: Theoretical Computer Science Seminar
- Presenter(s): Kewen Wu - Institute for Advanced Study
- Event Location: Conference Room 301 | Rutgers University | CoRE Building | 96 Frelinghuysen Road
- Event Additional Info: <p>See: <a href="https://theory.cs.rutgers.edu/theory_seminar">https://theory.cs.rutgers.edu/theory_seminar</a></p> <p> </p>
- Presentation Type: Stand Alone Presentation
- 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.