2025/11/18 by Daniel M. Kane, Anthony Ostuni, Kane, Daniel M. +3 · 1 citation
Computer Science · Mathematics · #Complexity and Algorithms in Graphs #Machine Learning and Algorithms #Markov Chains and Monte Carlo Methods
paper · pdf · doi:10.48550/arxiv.2511.14127
We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let f\colon \0,1\m → \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 D over \0,1\n. Then 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 \mathbbF2-polynomials. This extends the previous classification for generating symmetric distributions that are also uniform over their support.