2026-09-10T09:44:11Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:27770 2026-09-09T12:19:38Z ddc:004 open_access

Symmetric Distributions from Shallow Circuits Kane, Daniel M. Ostuni, Anthony Wu, Kewen Sampling distributions locality circuit complexity We characterize the symmetric distributions that can be (approximately) generated by shallow Boolean circuits. More precisely, let f: {0,1}^m → {0,1}ⁿ 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 𝒟 over {0,1}ⁿ. Then 𝒟 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 𝔽₂-polynomials. This extends the previous classification for generating symmetric distributions that are also uniform over their support. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Daniel M. Kane and Anthony Ostuni and Kewen Wu 2026 Is Part Of LIPIcs, Volume 392, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.APPROX/RANDOM.2026.53 urn:nbn:de:0030-drops-277707 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2026.53 eng https://creativecommons.org/licenses/by/4.0/legalcode