Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > KEYWORD > SYMMETRIC DISTRIBUTIONS:
Reports tagged with symmetric distributions:
TR25-183 | 18th November 2025
Daniel Kane, Anthony Ostuni, Kewen Wu

Symmetric Distributions from Shallow Circuits

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 ... more >>>




ISSN 1433-8092 | Imprint