{"id":"d7061a98-8125-4429-9b64-9ea4f4106f5c","arxiv_id":"2608.06256","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":7.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":0,"one_line_summary":"For symmetric Boolean functions, approximate signed-subcube weight is 2^Theta(D) and sparsity is 2^Theta(D) log n up to log factors, where D is the deepest transition depth.","lead":"This paper proves tight exponential bounds on the size and weight of signed subcube representations for symmetric Boolean functions, governed by the depth of the deepest transition. It also links these bounds to quantum query complexity through a Paturi-type characterization.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"The lower-bound proof invokes Paturi's theorem in a linear form that is false for centered majority leaves; the claimed 2^Ω(D) transfer collapses to 2^O(√D).","rationale":"The reader correctly identified the Paturi-based linear leaf bound as the weakest assumption. My stress-test goes one step further: the cited bound is not merely unverified in its uniform form; it is false for the centered leaves produced by the paper's own Lemma 4.1 in the majority case. Since almost the entire lower-bound machinery (Theorem 2.5 plus equation (15)) is designed to convert that linear bound into an exponential moment, losing linearity collapses the lower bound from 2^{Ω(D)} to 2^{Ω(√D)}. The oracle statement in Section 10 is internally inconsistent with standard facts: for majority, their formula gdeg_{1/3}=Θ(√{nD}) would imply Θ(n), contradicting the Θ(√n) approximate degree of majority. The same error contaminates the claimed quantum-query form in Corollary 2.6. I do not see a patch within the paper's framework: one would need a completely different lower-bound mechanism to recover 2^{Ω(D)} for majority. The upper-bound construction might still be salvageable, but the central classification theorem is not supported. This is a correctness-level flaw, not a cosmetic gap, so I recommend rejecting the current version (or requiring a major revision with a valid lower-bound proof).","tokens_in":10223,"tokens_out":38051,"duration_ms":414832,"concrete_test":"Take F to be the majority function on n variables, so D(F)=Θ(n), and run the leaf-dependent completion of Lemma 4.1. For a leaf with r free variables, the residual is the r-variable majority. Verify independently that its 1/3-approximate degree is Θ(√r), e.g. via the standard Chebyshev/Jordan construction or by checking against the cited quantum approximate-counting bound. Then recompute equation (15) with this bound: E[2^{c√R}] = 2^{Θ(√D)} rather than 2^{Ω(D)}. If no separate proof of ggwt_ε(majority)=2^{Ω(n)} is supplied, the lower-bound half of Theorems 2.1 and 2.4 fails.","verdict_should_be":"REJECT","load_bearing_attack":"The lower-bound half of Theorem 2.1 hangs on equation (15), which assumes every centered leaf with r free variables satisfies gdeg_{ε′}(f_F|_ρ) ≥ α r. Section 10 states the same Paturi input as gdeg_{1/3}(f_F) = Θ(√{nD(F)}). For the majority function F(w)=1_{w≥n/2}, D(F)=Θ(n), so this formula would give approximate degree Θ(n). But the standard Paturi/Chebyshev bound for an r-variable threshold with a single centered transition is Θ(√r), and quantum approximate counting (cited in the paper) gives the same Θ(√n) upper bound. Thus the 'linear in r' form is not a uniformity issue; it is false in the benchmark case. In Lemma 4.1, when F is majority, every residual f_F|_ρ is again an r-variable majority (one transition at r/2), so its 1/3-approximate degree is Θ(√r), not αr. Replacing αr by c√r in equation (15) yields Φ = E[2^{c√R}] = 2^{Θ(√D)}, since R ∼ Bin(D,1/3) is concentrated at Θ(D). Theorem 2.5 then gives only ggwt ≥ 2^{Ω(√D)}. Consequently the universal lower bound ggwt_ε(f_F)=2^{Ω(D)} and the logarithmic sparsity classification in Corollary 2.4 are not established by the main transfer argument; the paper's central quantitative claim rests on a misquoted Paturi theorem.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper studies approximate generalized weight and generalized sparsity of symmetric Boolean functions in the dictionary of subcube indicators (generalized monomials). For a symmetric function f_F(x)=F(|x|), let D(F) be the maximum distance of a transition of F from the nearest endpoint. The main results are: (i) an upper bound ggwt_ε(f_F) ≤ 2^{O(D(F) log(2/ε))} and a matching lower bound ggwt_ε(f_F) ≥ 2^{Ω_ε(D(F))}, giving ggwt_ε = 2^{Θ_ε(D(F))} uniformly in n and transition pattern; (ii) analogous upper and lower bounds for approximate generalized sparsity, yielding log(^gspar_ε(f_F)+1) = Θ_ε(D(F)+log log n) for D(F)≥2; (iii) a general dual exponential-profile transfer theorem (Theorem 2.5) producing signed measures with controlled subcube discrepancy; and (iv) a corollary relating log ggwt_ε to the square of quantum query complexity divided by n. The upper bounds are proved via symmetrization, Jackson approximation of edge profiles, a ternary output amplifier, and empirical sparsification; the lower bounds via a two-sided restriction tree with leaf-dependent centering of a deepest transition and a Paturi-type lower bound on the approximate degree of the residual.","tokens_in":32,"tokens_out":43469,"duration_ms":1082458,"significance":"The claimed classification, if it stands, is a complete characterization of approximate generalized weight and logarithmic-scale sparsity for symmetric functions in the subcube dictionary, with constants uniform in n and in the transition pattern. The paper is largely self-contained, introduces no fitted parameters, and states explicit quantitative bounds. Its transfer theorem (Theorem 2.5) is a flexible tool that may have applications beyond symmetric functions, and the connection to quantum query complexity (Corollary 2.6) is elegant. The proofs are detailed, with constructive lemmas (empirical sparsification, edge approximation, amplifier) that appear correct. The main risk flagged in the review process—that the lower bound misuses Paturi's theorem—does not survive scrutiny: the centered residual is a threshold with transition depth Θ(r), so its approximate degree is Θ(r).","major_comments":[{"comment":"The transfer uses the assertion that every centered leaf with r free variables satisfies gdeg_{ε′}(f_F|_ρ) ≥ α r. The stress-test worry is that the residual might be a majority-type threshold with approximate degree Θ(√r). That worry does not land: because the residual has a transition at depth ⌈r/2⌉ (Lemma 4.1), Paturi's theorem in its standard form (quoted by the paper in Section 10 as gdeg_{1/3}(f_F) = Θ(√(nD(F)))) yields gdeg_{ε′}(f|_ρ) = Θ(√(r · ⌈r/2⌉)) = Θ(r) for every fixed ε′ < 1/2, with constants independent of n and of the transition pattern. The linear lower bound is therefore valid, and equations (15) and the 2^{Ω(D)} conclusion are sound. The authors should nevertheless write out this two-line derivation, since the current sentence 'Paturi's theorem gives ...' is terse.","section":"Section 4, proof of the lower bound in Theorem 2.1, and equation (15)"}],"minor_comments":[{"comment":"The phrase 'exact singleton representation, whose support and weight are at most 2n ≤ 2^{2D}' is ambiguous and likely a typo: the exact representation as a sum over point masses has support and weight at most 2^n, not 2n. The bound still works because n < 2D implies 2^n < 2^{2D}, but the notation should be corrected and the representation defined.","section":"Section 8, proof of the upper bound in Theorem 2.1"},{"comment":"The constant α_{ε′} is introduced without an explicit statement of its origin. Since Paturi's theorem is stated in Section 10 only for error 1/3, the authors should note that the Θ(√(nD(F))) formula holds for every fixed ε′ < 1/2 with constants depending only on ε′.","section":"Section 4, equation (15)"},{"comment":"The lifting map L_ρ φ_ρ is not explicitly defined; a one-sentence definition would improve readability for readers not familiar with the restriction-tree framework.","section":"Section 3, proof of Theorem 2.5"},{"comment":"In the construction of t_±(z), the constants 1/10 and 4/5 depend on η0 being sufficiently small; the paper might state for clarity that η0 is chosen after fixing these constants, rather than the reverse order.","section":"Section 6, Lemma 6.2"}],"recommendation":"minor_revision","confidential_remarks":"The paper is technically solid and the central claims are believable. The referee report's conditional verdict was driven by a skepticism that, after careful reading, does not hold: the Paturi application in the lower-bound transfer is valid because the centered residual has transition depth Θ(r). The remaining issues are presentation-level (the '2n' typo, the terse Paturi step, and minor definitional gaps). I see no obstacles to publication after a minor revision. The acknowledgment of GPT assistance is transparent and not a concern."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The paper is a serious piece of Boolean function analysis. It gives the first complete classification of approximate generalized weight for symmetric functions in the subcube dictionary, plus a log-scale sparsity classification, and connects weight to squared quantum query complexity. The main transfer machinery—exponential restriction profiles, leaf-dependent centering, and the dual witness—is new and well executed. I went through the lower-bound proof with the stress-test objection in mind, and it doesn't hold. For a residual with r free variables and a transition centered at r/2, Paturi gives approximate degree Θ(r), not Θ(√r). The paper's own equation (30) is consistent: majority has D(F)=Θ(n), so its approximate degree is Θ(n), and quantum approximate counting also gives Θ(n) for majority, not Θ(√n). So the 2^Ω(D) lower bound stands.\n\nThe upper bound side is also plausible. The constant-error edge approximation, the ternary output amplifier, and the empirical sparsification fit together, and the absorbed polynomial factors are harmless given the exponential target.\n\nThe real soft spot is the n<2D edge case in Section 8. The paper asserts an 'exact singleton representation' with support and weight at most 2n and gives no proof or reference. That's not obviously true; for a centered threshold like majority on 5 variables, the exact generalized weight looks like it could be much larger than 2n. If that claim fails, the upper bounds for small n relative to D would need another argument. This is patchable, but it's a genuine gap in the written proof.\n\nMinor issues: the coefficient estimate 4B·7^m is clearly a loose bound, and a few places absorb 'polynomial factors' without spelling them out. None of these threaten the main theorems.\n\nAs a citation pattern, the paper builds appropriately on CDL26 and other prior work, and the GPT acknowledgment is transparent. I'd send this to a serious referee. The referee should ask for a proof of the singleton representation and maybe a clearer treatment of the n<2D regime, but I'd expect the main results to survive.\n\nWho's the audience: anyone working on polynomial representations, approximate degree, or symmetric functions. The Paturi-type query connection is a nice tie-in.","headline":"A substantial and probably correct classification of signed-subcube weight for symmetric functions; the Paturi objection doesn't land, but the n<2D edge case needs proof.","tokens_in":11054,"tokens_out":11521,"would_cite":true,"duration_ms":103351,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["68Q17","68Q12","94C10","41A10"],"pacs":[],"model":"deepseek-v4-flash","headline":"Approximate signed-subcube weight of every nonconstant symmetric function is $2^{\\Theta(D(F))}$, where $D(F)$ is the deepest transition depth.","keywords":["symmetric Boolean functions","generalized monomials","subcube indicators","generalized weight","generalized sparsity","approximate degree","quantum query complexity","restriction trees"],"falsifier":"Enumerate all symmetric Boolean functions for $n\\le 12$, solve the linear program defining $\\mathrm{ggwt}_\\varepsilon$ in Lemma 5.1 at one fixed $\\varepsilon$, and check that every nonconstant function obeys $2^{c_\\varepsilon D}\\le \\mathrm{ggwt}_\\varepsilon(f_F)\\le 2^{C_\\varepsilon D}$; a single violation of the claimed exponential dependence would refute Theorem 2.1.","tokens_in":10009,"feed_emoji":"🧮","tokens_out":15299,"duration_ms":146553,"temperature":0.7,"pith_summary":"This paper proves that the approximate cost of representing a symmetric Boolean function as a signed sum of subcube indicators is determined by a single number: $D(F)$, the depth of the function's deepest transition. For every fixed approximation error $0<\\varepsilon<1/2$ and every nonconstant symmetric function, the total coefficient weight of the cheapest $\\varepsilon$-approximating signed subcube combination is exactly $2^{\\Theta_\\varepsilon(D(F))}$, uniformly in the dimension $n$ and in the arrangement of transitions. The same parameter controls the logarithm of the number of subcubes, the generalized sparsity: when $D(F)\\ge 2$, $\\log(\\widehat{\\mathrm{gspar}}_\\varepsilon(f_F)+1)=\\Theta_\\varepsilon(D(F)+\\log\\log(n+2))$. Because Paturi's theorem identifies approximate degree with $\\Theta(\\sqrt{nD(F)})$ for symmetric functions, this gives a Paturi-type theorem for the subcube dictionary and ties signed-subcube weight to quantum query complexity. A reader should care because it reduces a seemingly high-dimensional approximation question to one geometric parameter of the truth table.","feed_headline":"Deepest transition depth alone sets signed-subcube cost","feed_subtitle":"For symmetric functions, signed-subcube approximation cost is exponential in the deepest transition depth alone.","key_machinery":"The machinery is a two-sided restriction tree that queries exactly $D(F)$ coordinates and completes the remaining coordinates in a leaf-dependent way so that one deepest transition of $F$ is centered in the residual function; at a random leaf the number $R$ of free variables is $\\mathrm{Bin}(D,1/3)$. For a generalized monomial $M$, the paper tracks the exponential potential $Z_\\rho(M)=2^{\\deg(M|_\\rho)}$ when $M$ survives a leaf restriction $\\rho$, and this potential has expectation at most one because the three branches 0, 1, and $*$ contribute 0, 1, and 2. Paturi's theorem supplies approximate degree at least $\\alpha R$ at each centered leaf, so the expectation of $2^{\\alpha R}$ is exponential in $D$, giving the lower bounds through a dual averaging argument. On the upper side, exponential profiles $r^w$ and $r^{n-w}$ are shown to have generalized weight at most one; Jackson approximation handles the whole edge pattern with one polynomial, a ternary output amplifier reduces the error from constant to $\\varepsilon$ while inflating coefficient mass by $2^{O(D\\log(1/\\varepsilon))}$, and an empirical sparsification lemma realizes each $r^w$ by a short average of subcubes, introducing the factor $\\log(n+1)$.","core_discovery":"The central claim is Theorem 2.1: with $\\varepsilon\\in(0,1/2)$ fixed, every nonconstant symmetric Boolean function $f_F(x)=F(|x|)$ satisfies $\\mathrm{ggwt}_\\varepsilon(f_F)=2^{\\Theta_\\varepsilon(D(F))}$, where $D(F)=\\max_{t:F(t-1)\\neq F(t)}\\min\\{t,n-t+1\\}$; the constants in $\\Theta_\\varepsilon$ depend only on $\\varepsilon$, not on $n$ or on the transition pattern. Corollary 2.4 extends this to sparsity: $\\log(\\widehat{\\mathrm{gspar}}_\\varepsilon(f_F)+1)=\\Theta_\\varepsilon(D(F)+\\log\\log(n+2))$ for $D(F)\\ge 2$, and functions with $D(F)=1$ have exact sparsity and weight at most three. The proof gives quantitative bounds $2^{O(D\\log(1/\\varepsilon))}$ from above and $2^{\\Omega(D)}$ from below, and a dual witness with constant correlation to the target but exponentially small correlation with every subcube indicator. It also derives $\\log(\\mathrm{ggwt}_\\varepsilon(f_F)+1)=\\Theta_\\varepsilon(Q_{1/3}(f_F)^2/n)$, matching the known quantum query complexity of symmetric functions.","pith_inferences":["The transfer mechanism is not inherently symmetric: any Boolean function whose restriction leaves carry linearly large approximate degree would inherit the same exponential lower bound; finding a genuinely nonsymmetric class with such a profile is the main structural open problem the paper states.","The logarithmic sparsity classification suggests that at the original scale the true sparsity may be a product of a function of $D$ and $\\log n$ rather than their maximum; the paper's product-versus-maximum gap is the next quantitative target.","Because the dual witness is explicit, the constructed distribution could be turned into a concrete weak-learning separation for conjunction-based hypothesis classes, and possibly into query or communication lower bounds in standard learning models."],"forward_implications":["For every fixed $0<\\varepsilon<1/2$, the approximate generalized weight of a nonconstant symmetric function is $2^{\\Theta_\\varepsilon(D(F))}$, with constants independent of $n$ and of the transition pattern.","For $D(F)\\ge 2$, the logarithm of approximate generalized sparsity is $\\Theta_\\varepsilon(D(F)+\\log\\log(n+2))$, so the ambient dimension enters only through a double logarithm.","Every symmetric function with $D(F)=1$ has exact generalized sparsity and weight at most three.","The logarithmic generalized weight of a symmetric function equals $\\Theta_\\varepsilon(Q_{1/3}(f_F)^2/n)$, which connects signed-subcube representation to bounded-error quantum query complexity.","The dual transfer yields a signed measure with constant correlation to $f_F$ and exponentially small correlation with every subcube indicator, giving a distribution on which every conjunction has exponentially small edge."],"supporting_citations":[{"why":"Supplies Paturi's theorem, the approximate-degree lower bound linear in the number of free variables at centered leaves that drives the exponential lower bound.","marker":"[Pat92]"},{"why":"Introduces the two-sided restriction trees and the one-monomial potential bound that the paper's transfer and both lower bounds build on.","marker":"[CDL26]"},{"why":"Provides the algebraic Jackson inequality used to approximate the full edge profile by one low-degree polynomial with controlled coefficient mass.","marker":"[DL93]"},{"why":"Gives the polynomial method used to prove the lower bound on bounded-error quantum query complexity.","marker":"[BBC+01]"},{"why":"Supplies quantum approximate counting, the algorithm used for the matching upper bound on quantum query complexity.","marker":"[BHMT02]"},{"why":"Gives explicit symmetric dual witnesses for approximate degree, making the lifted signed measure in the dual transfer explicit.","marker":"[BT15]"}],"fun_headline_variants":["Signed-subcube cost exponential in transition depth","Transition depth alone pins down signed-subcube weight","Exponential signed-subcube weight from transition depth alone","Quantum query complexity tied to signed-subcube approximation"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that Paturi's theorem gives a fixed positive constant $\\alpha_\\varepsilon$ such that at every centered leaf with $r$ free variables the approximate degree is at least $\\alpha_\\varepsilon r$, uniformly in $n$ and in the transition pattern; if that constant could shrink to zero, the $2^{\\Omega(D)}$ lower bound would fail.","fun_headline_variants_meta":{"raw":{"variants":["Signed-subcube cost exponential in transition depth","Transition depth alone pins down signed-subcube weight","Exponential signed-subcube weight from transition depth alone","Quantum query complexity tied to signed-subcube approximation"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.00072,"raw_usage":{"total_tokens":3184,"prompt_tokens":852,"completion_tokens":2332,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":468,"completion_tokens_details":{"reasoning_tokens":2273}},"tokens_in":468,"tokens_out":2332,"duration_ms":18207,"temperature":1.0,"reasoning_tokens":2273,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-07T11:19:02.126032+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Enumerate all symmetric Boolean functions for $n\\le 12$, solve the linear program defining $\\mathrm{ggwt}_\\varepsilon$ in Lemma 5.1 at one fixed $\\varepsilon$, and check that every nonconstant function obeys $2^{c_\\varepsilon D}\\le \\mathrm{ggwt}_\\varepsilon(f_F)\\le 2^{C_\\varepsilon D}$; a single violation of the claimed exponential dependence would refute Theorem 2.1.","supporting_citations":[],"review_version":1}