A Paturi Theorem for Signed Subcube Representations

Hangyu Liu

REVIEW 1 major objections 4 minor 12 references

A Paturi Theorem for Signed Subcube Representations

T0 review · 1 major / 4 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read Approximate signed-subcube weight of every nonconstant symmetric function is $2^{\Theta(D(F))}$, where $D(F)$ is the deepest transition depth.

desk verdict 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. read the letter →

arxiv 2608.06256 v1 pith:3QJRSSL2 submitted 2026-08-06 cs.CC

Hangyu liu This is my paper · ORCID

classification cs.CC MSC 68Q1768Q1294C1041A10

keywords symmetricBooleanfunctionsgeneralizedmonomialssubcubeindicatorsweightsparsityapproximatedegreequantumquerycomplexityrestrictiontrees

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

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.

What carries the argument

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)$.

What would settle it

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.

Watch

Extended reading notes

Core claim

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.

Load-bearing premise

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.

Editorial extensions

If this is right

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.

Reading between the lines

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

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.

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

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.

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

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

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

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

Who's the audience: anyone working on polynomial representations, approximate degree, or symmetric functions. The Paturi-type query connection is a nice tie-in.

Referee Report

1 major / 4 minor

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.

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 (1)

[Section 4, proof of the lower bound in Theorem 2.1, and equation (15)] 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.

minor comments (4)

[Section 8, proof of the upper bound in Theorem 2.1] 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 4, equation (15)] 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 3, proof of Theorem 2.5] 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 6, Lemma 6.2] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No circularity found: all load-bearing steps rely on external theorems or independent constructions, not on the paper's own conclusions.

full rationale

The paper's derivation chain does not contain a circular step in the sense of this analysis. The central lower bound (Theorem 2.1) is obtained by constructing a two-sided restriction tree, applying Paturi's theorem [Pat92] to residual symmetric functions, and then invoking the dual exponential-profile transfer (Theorem 2.5). Paturi's theorem is an external classical result, not an input that is equivalent to the claimed generalized-weight bound. The transfer theorem itself proves a general implication from approximate-degree lower bounds at leaves to generalized-weight lower bounds; it does not assume the target quantity. The upper bounds use independent machinery: Jackson approximation, Chebyshev coefficient estimates, an exponential-profile dictionary, and an empirical sparsification lemma. No parameter is fitted to a subset of the target data and then renamed a prediction. There are no self-citations by the author, so patterns 3, 4, and 5 do not arise. The stated 'quantum query complexity' relation in Corollary 2.6 follows by combining Paturi's characterization with the polynomial method and quantum approximate counting, both external results with standard proofs sketched in the paper. The skeptical concern that Paturi's theorem is applied in a linear form that may be false for centered majority residual functions is a correctness or soundness issue, not a circularity issue: it alleges a misstatement of an external theorem, not that the paper's conclusion is equivalent to its own assumption by construction. Per the review rules, such concerns belong under correctness risk rather than circularity. The derivation is therefore self-contained relative to external benchmarks, and no circularity score above zero is warranted.

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

The central results use no fitted parameters. They rely on standard background: Paturi's theorem for symmetric approximate degree, the restriction-tree setup of [CDL26], Jackson's inequality, LP duality for approximate degree, and Hoeffding/Chernoff bounds. The unproven exact singleton representation in the n<2D edge case is an ad-hoc gap rather than an axiom.

assumptions (6)

standard math Paturi's theorem: for symmetric Boolean functions on r variables with deepest transition depth d, gdeg_epsilon = Theta(sqrt(r d)), with constants depending only on epsilon.
Invoked in Section 4 to lower-bound leaf approximate degree by alpha r, and in Section 10 for gdeg_1/3 = Theta(sqrt(n D)).
domain assumption Two-sided restriction tree framework of [CDL26], with uniform random branching among 0,1,* and leaf-dependent completion.
The exponential one-monomial estimate (Lemma 3.1) and the transfer theorem operate inside this model; the paper does not redefine the model from first principles.
standard math Algebraic Jackson inequality for Lipschitz functions on [0,1].
Used in Lemma 6.1 to obtain a degree O(D) polynomial approximating the interpolated edge profile at constant error.
standard math LP duality for approximate degree: if gdeg_epsilon(g)>=k, there exists a function phi with l1 norm 1, correlation with g above epsilon, and zero correlation with all polynomials of degree below k.
Used in the proof of Theorem 2.5 to construct leaf witnesses.
standard math Quantum approximate counting error bound, equation (32).
Used in Section 10 to establish Q_1/3 = O(sqrt(n D)).
standard math Hoeffding and Chernoff concentration inequalities.
Used in Lemma 7.1 and Lemma 6.2 for random sampling and majority amplification.

how reviews work

0 comments

Cite this review

Pith. "Pith review of A Paturi Theorem for Signed Subcube Representations." pith.science (2026). https://pith.science/paper/3QJRSSL2

@misc{pith2026260806256,
  author       = {Pith},
  title        = {Pith review of: A Paturi Theorem for Signed Subcube Representations},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/3QJRSSL2}},
  note         = {Machine review of arXiv:2608.06256}
}

read the original abstract

We obtain exponential upper bounds on approximate generalized weight and generalized sparsity in terms of the deepest transition depth D(F), and show that these bounds are optimal up to constant factors in the exponent. We further characterize approximate generalized sparsity, establish a dual lower-bound framework based on exponential restriction profiles, and derive a Paturi-type characterization relating approximate generalized weight to quantum query complexity.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

12 extracted references · 8 canonical work pages

[1]

Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) , pages =

Chattopadhyay, Arkadev and Dahiya, Yogesh and Lovett, Shachar , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) , pages =. 2026 , note =. doi:10.1145/3798129.3800895 , url =

arXiv 2026
[2]

Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing , pages =

Paturi, Ramamohan , title =. Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing , pages =. 1992 , publisher =

work page 1992
[3]

Computational Complexity , volume =

Nisan, Noam and Szegedy, Mario , title =. Computational Complexity , volume =. 1994 , doi =

work page 1994
[4]

, title =

Sherstov, Alexander A. , title =. Computational Complexity , volume =. 2009 , doi =

work page 2009
[5]

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM 2012) , series =

Ada, Anil and Fawzi, Omar and Hatami, Hamed , title =. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM 2012) , series =. 2012 , publisher =

work page 2012
[6]

On the Spectral Properties of Symmetric Functions

Ada, Anil and Fawzi, Omar and Kulkarni, Raghav , title =. 2017 , eprint =. doi:10.48550/arXiv.1704.03176 , url =

work page Pith review arXiv doi:10.48550/arxiv.1704.03176 2017
[7]

, title =

Chattopadhyay, Arkadev and Mande, Nikhil S. , title =. 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) , series =. 2018 , publisher =

work page 2017
[8]

Journal of the ACM , volume =

Alon, Noga and Yuster, Raphael and Zwick, Uri , title =. Journal of the ACM , volume =. 1995 , doi =

work page 1995

Show all 12 references

[9]

Journal of the ACM , volume =

Beals, Robert and Buhrman, Harry and Cleve, Richard and Mosca, Michele and de Wolf, Ronald , title =. Journal of the ACM , volume =. 2001 , doi =. quant-ph/9802049 , archivePrefix =

2001 arXiv
[10]

and Lorentz, George G

DeVore, Ronald A. and Lorentz, George G. , title =. 1993 , isbn =

1993
[11]

Information and Computation , volume =

Bun, Mark and Thaler, Justin , title =. Information and Computation , volume =. 2015 , doi =. 1302.6191 , archivePrefix =

2015 arXiv
[12]

Quantum Amplitude Amplification and Estimation , booktitle =

Brassard, Gilles and H. Quantum Amplitude Amplification and Estimation , booktitle =. 2002 , doi =. quant-ph/0005055 , archivePrefix =

2002 arXiv

Pith tools

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

[1] [1]

Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) , pages =

Chattopadhyay, Arkadev and Dahiya, Yogesh and Lovett, Shachar , title =. Proceedings of the 58th Annual ACM Symposium on Theory of Computing (STOC 2026) , pages =. 2026 , note =. doi:10.1145/3798129.3800895 , url =

arXiv 2026

[2] [2]

Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing , pages =

Paturi, Ramamohan , title =. Proceedings of the Twenty-Fourth Annual ACM Symposium on Theory of Computing , pages =. 1992 , publisher =

work page 1992

[3] [3]

Computational Complexity , volume =

Nisan, Noam and Szegedy, Mario , title =. Computational Complexity , volume =. 1994 , doi =

work page 1994

[4] [4]

, title =

Sherstov, Alexander A. , title =. Computational Complexity , volume =. 2009 , doi =

work page 2009

[5] [5]

Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM 2012) , series =

Ada, Anil and Fawzi, Omar and Hatami, Hamed , title =. Approximation, Randomization, and Combinatorial Optimization: Algorithms and Techniques (APPROX/RANDOM 2012) , series =. 2012 , publisher =

work page 2012

[6] [6]

On the Spectral Properties of Symmetric Functions

Ada, Anil and Fawzi, Omar and Kulkarni, Raghav , title =. 2017 , eprint =. doi:10.48550/arXiv.1704.03176 , url =

work page Pith review arXiv doi:10.48550/arxiv.1704.03176 2017

[7] [7]

, title =

Chattopadhyay, Arkadev and Mande, Nikhil S. , title =. 37th IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2017) , series =. 2018 , publisher =

work page 2017

[8] [8]

Journal of the ACM , volume =

Alon, Noga and Yuster, Raphael and Zwick, Uri , title =. Journal of the ACM , volume =. 1995 , doi =

work page 1995