Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Revision(s):

Revision #1 to TR24-180 | 26th February 2025 05:27

Locally Sampleable Uniform Symmetric Distributions

RSS-Feed




Revision #1
Authors: Daniel Kane, Anthony Ostuni, Kewen Wu
Accepted on: 26th February 2025 05:27
Downloads: 21
Keywords: 


Abstract:

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{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 $\mathcal D$ with a symmetric support. We show that $\mathcal 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).



Changes to previous version:

We make a number of technical changes to remove the dependence on d in the final distance bound.


Paper:

TR24-180 | 13th November 2024 00:07

Locally Sampleable Uniform Symmetric Distributions





TR24-180
Authors: Daniel Kane, Anthony Ostuni, Kewen Wu
Publication: 19th November 2024 05:27
Downloads: 198
Keywords: 


Abstract:

We characterize the power of constant-depth Boolean circuits in generating uniform symmetric distributions. Let $f\colon\{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 $\mathcal D$ with a symmetric support. We show that $\mathcal 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).



ISSN 1433-8092 | Imprint