Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR25-183 | 18th November 2025 05:37

Symmetric Distributions from Shallow Circuits

RSS-Feed




TR25-183
Authors: Daniel Kane, Anthony Ostuni, Kewen Wu
Publication: 18th November 2025 09:39
Downloads: 25
Keywords: 


Abstract:

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 $\gamma$-biased product distributions for $\gamma$ 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.



ISSN 1433-8092 | Imprint