Symmetric Distributions from Shallow Circuits
Fuente:
arXiv
Enregistré dans:
| Auteurs principaux: | , , |
|---|---|
| Format: | Preprint |
| Publié: |
2025
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866918208088309760 |
|---|---|
| author | Kane, Daniel M. Ostuni, Anthony Wu, Kewen |
| author_facet | Kane, Daniel M. Ostuni, Anthony Wu, Kewen |
| contents | We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let $f\colon \{0,1\}^m \to \{0,1\}^n$ be a Boolean function where each output bit depends on at most $d$ input bits. Suppose the output distribution of $f$ evaluated on uniformly random input bits is close in total variation distance to a symmetric distribution $\mathcal{D}$ over $\{0,1\}^n$. Then $\mathcal{D}$ must be close to a mixture of the uniform distribution over $n$-bit strings of even Hamming weight, the uniform distribution over $n$-bit strings of odd Hamming weight, and $γ$-biased product distributions for $γ$ an integer multiple of $2^{-d}$. Moreover, the mixing weights are determined by low-degree, sparse $\mathbb{F}_2$-polynomials. This extends the previous classification for generating symmetric distributions that are also uniform over their support. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2511_14127 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Symmetric Distributions from Shallow Circuits Kane, Daniel M. Ostuni, Anthony Wu, Kewen Computational Complexity We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let $f\colon \{0,1\}^m \to \{0,1\}^n$ be a Boolean function where each output bit depends on at most $d$ input bits. Suppose the output distribution of $f$ evaluated on uniformly random input bits is close in total variation distance to a symmetric distribution $\mathcal{D}$ over $\{0,1\}^n$. Then $\mathcal{D}$ must be close to a mixture of the uniform distribution over $n$-bit strings of even Hamming weight, the uniform distribution over $n$-bit strings of odd Hamming weight, and $γ$-biased product distributions for $γ$ an integer multiple of $2^{-d}$. Moreover, the mixing weights are determined by low-degree, sparse $\mathbb{F}_2$-polynomials. This extends the previous classification for generating symmetric distributions that are also uniform over their support. |
| title | Symmetric Distributions from Shallow Circuits |
| topic | Computational Complexity |
| url | https://arxiv.org/abs/2511.14127 |