{"id":"e7f51e9b-3afa-4f08-9a18-599336258aa1","arxiv_id":"2511.14127","paper_version":2,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"Every symmetric distribution approximately sampleable by a d-local Boolean circuit is close to a mixture of uniform even/odd Hamming layers and γ-biased product distributions for γ a multiple of 2^{-d}, with F2-polynomial mixing weights.","lead":"This paper proves a structural classification: any symmetric distribution that can be approximately generated by a shallow Boolean circuit (each output bit depends on at most d inputs) must be close to a mixture of uniform even/odd-weight layers and product distributions with biases that are multiples of 2^{-d}. It extends earlier work that only handled uniform symmetric distributions, and it matters because it delimits exactly what random patterns NC^0 circuits can produce.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Lemma 4.24 applies Proposition 4.5 with A=k, but Proposition 4.5 requires A≥2^{100d}; for essentially all relevant ε, k<2^{100d}, so the main proof does not cover its stated parameter range.","rationale":"The reader's weakest_assumption field identifies Lemma 4.7 as the foundation, but the actual concern raised in the reader's rationale is the invalid use of Proposition 4.5 with A=k in Lemma 4.24. This is the most load-bearing internal gap: it breaks the proof of the main theorem for a broad range of ε, not just an edge case. The issue is concrete and fixable in principle, but as written the proof is incomplete. The reader's verdict of CONDITIONAL remains appropriate; our analysis does not move it. Agreement is partial because the reader's stated weakest assumption (Lemma 4.7) is not the same as the specific internal gap that appears load-bearing in our read.","tokens_in":47867,"tokens_out":14228,"duration_ms":125698,"concrete_test":"Re-derive Lemma 4.9 with A set to k = floor(log(1/ε)/C_d), tracking the variance bound Var[g] ≤ dn^2/A. Check whether Claim 4.12 still yields a 1/4 upper bound and whether Claim 4.14's event E_π still has probability at least 7/8 when A=k and k < 2^{100d}. If either fails, the proof of Proposition 4.5 cannot be applied with A=k, confirming the gap in Lemma 4.24.","verdict_should_be":"UNCHANGED","load_bearing_attack":"In the proof of Lemma 4.24 (Section 4.4), the authors set k = Θ_d(log(1/ε)) and define S as the set of input bits with degree at least n/k. They then invoke Proposition 4.5 with this A = k to obtain the k-tuple independence of the restricted functions. However, Proposition 4.5 (Section 4.1) explicitly assumes A ≥ 2^{100d} and ε < 2^{-cdA}. For any ε larger than a doubly exponential in d, k is far below 2^{100d}; e.g., for d=1, 2^{100} is astronomically large while k is at most a small multiple of log(1/ε). Hence the hypotheses of Proposition 4.5 are not satisfied. This is not a cosmetic issue: the proof of Lemma 4.9 uses A≥2^{100d} to bound the variance of the output weight by dn^2/2^{100d} and to ensure the event E_π in Claim 4.14 holds with high probability. If A=k, the variance bound becomes dn^2/k and the probability of E_π degrades, so the concentration argument collapses. Consequently, Lemma 4.24 is unproven for the parameter range ε ≥ 2^{-C_d 2^{100d}}, which includes all but doubly-exponentially small ε. Since Lemma 4.26 and Theorem 4.1 depend on Lemma 4.24, the central claim as stated is not established by the written proof.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":48224,"tokens_out":21455,"duration_ms":191144,"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":[{"comment":"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","section":"§4.4, proof of Lemma 4.24"}],"minor_comments":[{"comment":"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.","section":"§4.4, proof of Lemma 4.24"},{"comment":"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.","section":"§4.3, proof of Proposition 4.21, Claim 4.22"},{"comment":"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.","section":"§4.3, proof of Proposition 4.21"},{"comment":"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.","section":"§4.4, proof of Lemma 4.23"},{"comment":"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.","section":"Proposition 4.16"}],"recommendation":"major_revision","confidential_remarks":"The main theorem is plausible and the proof is extensive, but the application of Proposition 4.5 in Lemma 4.24 is a genuine load-bearing gap. In my view this is fixable within the scope of the paper: either strengthen Proposition 4.5 to handle A = k or use A = 2^{100d} and adjust the constants so the uncovered epsilon-range is vacuous. I do not see grounds for rejection, but the current manuscript does not prove the theorem as stated."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague—\n\nBottom 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.\n\nWhat'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.\n\nThe 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.\n\nSend 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.","headline":"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.","tokens_in":48702,"tokens_out":5369,"would_cite":true,"duration_ms":51609,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q87","94C10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Shallow circuits that generate near-symmetric distributions must produce a dyadic, parity-structured mixture.","keywords":["shallow circuits","symmetric distributions","bounded locality","sampling complexity","total variation distance","Hamming weight","F2 polynomials","distribution learning"],"falsifier":"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.","tokens_in":47723,"feed_emoji":"🎲","tokens_out":4886,"duration_ms":50107,"temperature":0.7,"pith_summary":"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.","feed_headline":"Symmetric outputs of shallow circuits reduce to dyadic mixtures","feed_subtitle":"Near-symmetric outputs of d-local circuits are even/odd layers plus dyadic-biased bits.","key_machinery":"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.","core_discovery":"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","pith_inferences":["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."],"forward_implications":["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."],"fun_headline_variants":["Shallow circuits yield near-symmetric outputs as dyadic mixtures","d-local circuits: symmetric outputs are even/odd plus dyadic bias","Symmetric outputs from shallow circuits reduce to dyadic mixtures","Near-symmetric distributions from d-local functions are dyadic mixtures","Symmetric outputs from shallow circuits: beyond uniform to dyadic"],"cache_read_input_tokens":2304,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Shallow circuits yield near-symmetric outputs as dyadic mixtures","d-local circuits: symmetric outputs are even/odd plus dyadic bias","Symmetric outputs from shallow circuits reduce to dyadic mixtures","Near-symmetric distributions from d-local functions are dyadic mixtures","Symmetric outputs from shallow circuits: beyond uniform to dyadic"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000782,"raw_usage":{"total_tokens":3283,"prompt_tokens":728,"completion_tokens":2555,"prompt_tokens_details":{"cached_tokens":256},"prompt_cache_hit_tokens":256,"prompt_cache_miss_tokens":472,"completion_tokens_details":{"reasoning_tokens":2468}},"tokens_in":472,"tokens_out":2555,"duration_ms":16613,"temperature":1.0,"reasoning_tokens":2468,"cache_read_input_tokens":256,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-03T21:39:36.971030+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}