Symmetric Distributions from Shallow Circuits

Anthony Ostuni; Daniel M. Kane; Kewen Wu

REVIEW 1 major objections 5 minor 4 references

Symmetric Distributions from Shallow Circuits

T0 review · 1 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Shallow circuits that generate near-symmetric distributions must produce a dyadic, parity-structured mixture.

desk verdict A natural, likely correct extension of KOW25—but Lemma 4.24's parameter handling has a real gap that needs fixing before I'd bet on the proof as written. read the letter →

arxiv 2511.14127 v2 pith:QGTGLJMC submitted 2025-11-18 cs.CC

Daniel M. Kane , Anthony Ostuni , Kewen Wu This is my paper · ORCID

classification cs.CC MSC 68Q1768Q8794C10

keywords shallowcircuitssymmetricdistributionsboundedlocalitysamplingcomplexitytotalvariationdistanceHammingweightF2polynomialsdistributionlearning

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

The paper proves a classification theorem: any Boolean function whose output bits each depend on at most d input bits, and whose output distribution is ε-close to a symmetric distribution, must itself be δ-close (with δ tending to 0 as ε tends to 0) to a simple mixture. The allowable mixture components are the uniform distribution over even-weight strings, the uniform distribution over odd-weight strings, and product distributions whose bias is an integer multiple of 2^-d. The mixing weights are pinned down by low-degree sparse F2-polynomials, so the entire family is exactly samplable by constant-locality circuits. This settles a broad question left open by earlier work that only handled uniform symmetric distributions; it also gives an efficient learning algorithm for locally sampleable symmetric distributions.

What carries the argument

The argument runs through four linked tools: the symmetrization identity ∥P−Q∥_TV = Θ(∥|P|−|Q|∥_TV + ∥P−P_sym∥_TV), which reduces the problem to classifying Hamming-weight distributions; conditioning on high-degree input bits, which forces weight concentration near integer multiples of n/2^d; Kolmogorov-distance bounds obtained from k-wise independence of output tuples; and an approximate-continuity result built from hypergraph neighborhoods and sums of independent integer random variables. The mixing weights are finally encoded by degree-d F2-parity polynomials that track the parity of the output weight, giving the structural form of the theorem.

What would settle it

Take the simplest d-local function producing independent bits with a non-dyadic bias and compare its output distribution to the uniform distribution over weight-k strings for k/n with binary representation error δ; check whether the total variation distance satisfies the claimed lower bound 1 − 4√(2n)exp(−nδ^{40d}). A violation of that bound would break the foundation of the proof; alternatively, exhibit a d-local f whose output is ε-close to symmetric but whose distance to every mixture of the stated form is Ω(1) independent of ε, which would refute the theorem.

Watch

Extended reading notes

Core claim

Theorem 4.1 states that if f:{0,1}^m→{0,1}^n is d-local and f(U_m) is ε-close in total variation to a symmetric distribution D over {0,1}^n, then for n sufficiently large in terms of d and ε, f(U_m) is O_d((1/log(1/ε))^{1/5})-close to a mixture of the uniform distribution over even-weight strings, the uniform distribution over odd-weight strings, and γ-biased product distributions for γ an integer multiple of 2^-d. Moreover, the mixing weights are determined by at most 2^C degree-d F2-polynomials with O_d(n) monomials each. In the paper's own framing, this extends the previous six-distribution classification of uniform symmetric distributions to all symmetric distributions, and it shows the

Load-bearing premise

The whole proof rests on an unproved earlier lemma asserting that any d-local function is statistically far from the uniform distribution over strings of weight k whenever k/n is far from every integer multiple of 2^-d; if that lemma fails, the first reduction step and hence the characterization collapse.

Editorial extensions

If this is right

If the theorem is correct, the class of approximately symmetric distributions generatable by bounded-locality circuits is exactly the convex hull of dyadic product distributions plus even/odd weight layers; no other symmetric distribution can be approached.
Every mixture of the stated form is itself exactly samplable by an O_d(1)-local function, so the characterization is tight as a generative class.
A black-box corollary is an efficient learner: O_d(1/ε^2) samples suffice to learn any locally sampleable symmetric distribution to error ε in total variation.
The earlier six-case classification for uniform symmetric distributions follows as a special case.
Exact sampling admits distributions outside the mixture class (the paper's Example 1.3), so the theorem's δ cannot be driven to zero without adding new components.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

If the classification is right, it implies a structural dichotomy: shallow circuits either produce nearly independent dyadic-biased bits or a global parity layer, and all other correlations wash out.
A natural strengthening, which the paper conjectures, is linear error O(ε) in total variation; verifying or refuting it would determine whether the learning result extends to all ε, including large noise.
The parity-polynomial representation of the mixing weights suggests that the even/odd components are governed by the low-degree Fourier spectrum of the circuit, so one might recover the weight structure of an unknown locally sampleable distribution by estimating low-degree parities.
Example 1.3 hints at an exact characterization involving bitwise functions of even/odd layers; probing small d against that conjecture would map the boundary between approximate and exact sampling.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague—

Bottom line: this is a genuine extension of the KOW25 classification, from uniform symmetric distributions to arbitrary symmetric ones, and the main theorem is probably right. But the written proof has a gap at Lemma 4.24 that needs repairing before I'd take it as established.

What's new and worth credit: the theorem characterizes locally sampleable symmetric distributions as mixtures of dyadic-biased binomials plus even/odd weight layers, with the mixing weights controlled by degree-d sparse F2 polynomial evaluations. That is a natural next step from [KOW25], and the paper supplies a detailed four-step argument: conditioning on high-degree inputs, Kolmogorov-distance control, an approximate continuity result, and a mixing-weight construction. The learning application is a nice dividend, and Appendix A's exact-sampling counterexample is a useful sanity check showing the approximate classification is not accidentally exact. The paper is honest about its limitations, and the self-citations are to published, peer-reviewed results used as lemmas—no circularity problem there.

The soft spot is real and exactly where the stress test points. In Lemma 4.24, the proof defines the high-degree set S with threshold n/k and then invokes Proposition 4.5 with A=k. But Proposition 4.5 explicitly requires A≥2^{100d}, and its proof (via Lemma 4.9, the variance bound, and Claim 4.14) genuinely uses that lower bound to keep the variance at dn^2/2^{100d} and to make the event E_π work. For any reasonable ε, k is far below 2^{100d}, so the invoked result does not apply. Since Lemma 4.24 is the pivot for the whole theorem, the proof as written does not cover its stated parameter range. This is fixable, not fatal. The obvious repair—set A = max(k, 2^{100d}), or simply always condition on bits of degree ≥ n/2^{100d}—lets the rest of the argument go through with constants absorbed into O_d. The γ=1/2 term in Lemma 4.23 retains an A-dependence, but with A a d-constant it folds into the O_d. So I believe the theorem is true, but the manuscript needs revision.

Send it to peer review. The referee should ask the authors to fix Section 4.4's parameter handling and make the ε-range explicit in each lemma. This is a serious paper that deserves referee time.

Referee Report

1 major / 5 minor

Summary. The paper characterizes the symmetric distributions that can be approximately sampled by d-local Boolean circuits, i.e., by NC^0 functions with constant locality. The main theorem (Theorem 4.1) states that if the output distribution f(U_m) is epsilon-close to a symmetric distribution, then it is O_d(log(1/epsilon)^(-1/5))-close to a mixture of: the uniform distribution on even-weight strings, the uniform distribution on odd-weight strings, and gamma-biased product distributions with gamma an integer multiple of 2^(-d); moreover, the mixing weights are controlled by low-degree, O_d(n)-sparse F_2-polynomials. The proof is organized into a conditioning argument on high-degree input bits, a Kolmogorov-distance comparison to binomials, an approximate-continuity step for the output weight distribution, and a final assembly that also gives the polynomial description of the mixing weights.

Significance. The contribution is substantial if the result holds: it substantially extends the uniform-symmetric classification of [KOW25] to all symmetric distributions and gives a quantitative, structural description of the distributions samplable by bounded-locality circuits. The paper is careful to build on published theorems ([KOW24], [KOW25], [GOWZ10], [CHH+20]) rather than to reprove or circularly reuse its own claims; the main heavy lifting is new. The explicit polynomial representation of the mixing weights, with a constructive sampling argument in Remark 4.2, is a genuine strength. The manuscript is long but generally well organized and mostly careful in its quantitative bookkeeping.

major comments (1)

[§4.4, proof of Lemma 4.24] The proof of Lemma 4.24 sets S to be the set of input bits of degree at least n/k and then invokes Proposition 4.5 with the degree-threshold parameter A taken to be k. This application is outside the stated hypothesis of Proposition 4.5, which requires A >= 2^{100d} and epsilon < 2^{-cdA} (Section 4.1). Here k = Theta_d(log(1/epsilon)), so for every epsilon that is not doubly exponentially small in d we have k < 2^{100d}; moreover the condition epsilon < 2^{-cdk} is equivalent to epsilon < epsilon^{Omega_d(1)}, which is impossible for epsilon < 1. The threshold A >= 2^{100d} is not cosmetic in the proof of Proposition 4.5: Claim 4.14's concentration argument relies on the event E_pi whose probability bound requires each input bit in the restricted function to have degree at most n/2^{100d}, not merely n/k. Thus Lemma 4.24 is unproved in the parameter range needed for the main theorem, an

minor comments (5)

[§4.4, proof of Lemma 4.24] In the displayed equation comparing |f(U_m)| and P, the notation U^{[m]\(S∪R)} introduces an undefined set R; it should be U^{[m]\S}, matching the definition of f_gamma immediately above.
[§4.3, proof of Proposition 4.21, Claim 4.22] The claim says that X_{sigma,i} depends on at most d input bits. In fact it depends on all input bits affecting the neighborhood N(i), which is O_d(t) bits. The subsequent 2^{-dt} bound is still valid because t = O_d(1), but the sentence is inaccurate and should be corrected.
[§4.3, proof of Proposition 4.21] Lemma 3.3 is stated only for a balanced mixture, but it is applied to the non-balanced mixture E over the conditionings rho. The argument can be adapted by replacing the number of components with 2^{|S|}, as the text implicitly does, but the manuscript should state or prove this generalized form.
[§4.4, proof of Lemma 4.23] The chain of inequalities beginning 'C·(epsilon + kappa log(1/delta)) <= C·(epsilon + kappa log(1/delta)+delta) - O(delta)' is confusing: the first inequality appears tautological and the '-O(delta)' is unclear. Please rewrite this contradiction argument more explicitly.
[Proposition 4.16] In the gamma = 1/2 case, the displayed error term has a stray 'd' next to log(1/delta)^{O(d)}. The intended expression is log(1/delta)^{O(d)}/sqrt(A delta), but the typesetting should be corrected.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: prior self-citations are published building blocks, not re-imported conclusions.

full rationale

The paper's derivation chain is not circular. Theorem 4.1 is proved by reducing the full distribution to its Hamming-weight distribution (Lemma 3.4), then proving weight-distribution approximations via Lemma 4.24 and Lemma 4.26. Those lemmas rely on earlier work by the same authors, especially Lemma 4.7 [KOW24, Theorem 5.7] and Lemma 4.19 [KOW25, Theorem A.1], but they are used as independent prior theorems with stated assumptions that do not include the target result. The mixing weights are not fitted to the output distribution; they are constructed from the parity polynomials of the restricted functions, and the comparison to the relevant probabilities is derived from concentration and the triangle inequality, not assumed. The main extension over [KOW25] is the handling of arbitrary symmetric distributions rather than uniform symmetric ones, and this is achieved by new arguments in Propositions 4.5, 4.16, 4.21, and Lemmas 4.23-4.26. The only notable concern is a possible parameter-range gap in Lemma 4.24, where Proposition 4.5 is invoked with A=k although Proposition 4.5 requires A≥2^{100d}; this is a correctness/scope issue, not a circular reduction, because it does not make a conclusion identical to an input or rename a fitted quantity as a prediction. Overall, the central claim has independent content and does not collapse by construction into its own hypotheses.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

The central theorem introduces no new entities or fitted parameters. It depends on several external theorems from prior published work (some by the same authors), which are used as black boxes. The free-parameter list is empty because all proof constants (A, k, C_d) are existential and not fitted to data.

assumptions (6)

domain assumption Lemma 4.7 ([KOW24, Theorem 5.7]): if err(k/n,d) ≥ δ, then any d-local f satisfies ||f(U_m)-D_k||_{TV} ≥ 1 - 4√(2n) exp(-n δ^{40d}).
Invoked in Lemma 4.8 to show the output weight is typically close to an integer multiple of n/2^d; this is the first structural step. Not re-proved here.
domain assumption Lemma 4.15 ([GOWZ10, Theorem I.5]): k-wise independent γ-biased bits fool threshold functions in Kolmogorov distance up to O(polylog(k)/√k).
Used in Proposition 4.16 to compare weight distributions to binomials; central to Step 2.
domain assumption Theorem 4.17 ([CHH+20, Theorem 3.1]): low-degree F2-polynomials can be re-randomized by a small set of coordinates.
Used in Proposition 4.16 to handle parity in the γ=1/2 case.
domain assumption Lemma 4.18 ([KOW24, Corollary 4.11]): hypergraphs of max degree d have many small non-adjacent neighborhoods after removing few edges.
Used in Proposition 4.21 to find independent output neighborhoods for the continuity argument.
domain assumption Lemma 4.19 ([KOW25, Theorem A.1]): density comparison for sums of independent bounded integer variables.
Used in Proposition 4.21 to derive the approximate-continuity of the output weight distribution.
standard math Standard probability bounds (Hoeffding, Chernoff, Chebyshev, Fact 3.11) and Fourier analytic facts (Fact 3.10).
Used throughout §4; standard results assumed without proof.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Symmetric Distributions from Shallow Circuits." pith.science (2026). https://pith.science/paper/QGTGLJMC

@misc{pith2026251114127,
  author       = {Pith},
  title        = {Pith review of: Symmetric Distributions from Shallow Circuits},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/QGTGLJMC}},
  note         = {Machine review of arXiv:2511.14127}
}

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

4 extracted references · 1 linked inside Pith

[2012]

X i∈Sw B(X) i =a # −Pr

3, 13 [Vio14] Emanuele Viola. Extractors for circuit sources.SIAM Journal on Computing, 43(2):655–672, 2014. 3, 13 [Vio20] Emanuele Viola. Sampling lower bounds: boolean average-case and permutations. SIAM Journal on Computing, 49(1):119–137, 2020. 3, 6, 13, 15 [Vio23] Emanuele Viola. New sampling lower bounds via the separator. In38th Computational Compl...

arXiv 2014
[2013]

On the Fourier tails of bounded functions over the discrete cube

4 [DFKO06] Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell. On the Fourier tails of bounded functions over the discrete cube. InProceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 437–446, 2006. 16 [DGJ+10] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A Servedio, and Emanuele Viola. Bounded indepe...

arXiv 2006
[2020]

Extractors for near logarithmic min-entropy

8, 26 [CS16] Gil Cohen and Leonard J Schulman. Extractors for near logarithmic min-entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 178–187. IEEE, 2016. 3 [CT06] Thomas M Cover and Joy A Thomas. Elements of information theory, 2006. 15 [CZ16] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractor...

2016
[2025]

Improved bounds for the sunflower lemma.Annals of Mathematics, 194(3):795–815, 2021

3 [AL WZ21] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma.Annals of Mathematics, 194(3):795–815, 2021. 12 [Bab87] L´ aszi´ o Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26(1):51–53, 1987. 3, 11 [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, Dav...

2021

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.

[1] [2012]

X i∈Sw B(X) i =a # −Pr

3, 13 [Vio14] Emanuele Viola. Extractors for circuit sources.SIAM Journal on Computing, 43(2):655–672, 2014. 3, 13 [Vio20] Emanuele Viola. Sampling lower bounds: boolean average-case and permutations. SIAM Journal on Computing, 49(1):119–137, 2020. 3, 6, 13, 15 [Vio23] Emanuele Viola. New sampling lower bounds via the separator. In38th Computational Compl...

arXiv 2014

[2] [2013]

On the Fourier tails of bounded functions over the discrete cube

4 [DFKO06] Irit Dinur, Ehud Friedgut, Guy Kindler, and Ryan O’Donnell. On the Fourier tails of bounded functions over the discrete cube. InProceedings of the thirty-eighth annual ACM symposium on Theory of computing, pages 437–446, 2006. 16 [DGJ+10] Ilias Diakonikolas, Parikshit Gopalan, Ragesh Jaiswal, Rocco A Servedio, and Emanuele Viola. Bounded indepe...

arXiv 2006

[3] [2020]

Extractors for near logarithmic min-entropy

8, 26 [CS16] Gil Cohen and Leonard J Schulman. Extractors for near logarithmic min-entropy. In 2016 IEEE 57th Annual Symposium on Foundations of Computer Science (FOCS), pages 178–187. IEEE, 2016. 3 [CT06] Thomas M Cover and Joy A Thomas. Elements of information theory, 2006. 15 [CZ16] Eshan Chattopadhyay and David Zuckerman. Explicit two-source extractor...

2016

[4] [2025]

Improved bounds for the sunflower lemma.Annals of Mathematics, 194(3):795–815, 2021

3 [AL WZ21] Ryan Alweiss, Shachar Lovett, Kewen Wu, and Jiapeng Zhang. Improved bounds for the sunflower lemma.Annals of Mathematics, 194(3):795–815, 2021. 12 [Bab87] L´ aszi´ o Babai. Random oracles separate PSPACE from the polynomial-time hierarchy. Information Processing Letters, 26(1):51–53, 1987. 3, 11 [BEHW89] Anselm Blumer, Andrzej Ehrenfeucht, Dav...

2021