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

Revisions: 1

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