CS Paper Radar

Sharp Degree Bounds for Putinar Certificates in Terms of the Positivity Margin via Analytic Sums of Squares

Yuxiang Zhao, Ting Gan

cs.CL ·submitted 2026-10-18 23:10 UTC · v2
theory

Abstract

We establish sharp degree bounds for Putinar sum-of-squares (SOS) certificates in terms of the positivity margin $δ$. For any fixed Archimedean quadratic module with prescribed generators and any fixed degree bound on the objective, normalized polynomial objectives admit a uniform certificate-degree upper bound of $O(δ^{-1/2}\log^2(2/δ))$. The bound is sharp: we construct a matching lower-bound example in three variables. We further show that the number of inequality generators affects the optimal degree bound. For quadratic modules with at most two inequality generators, the bound improves to $O(δ^{-1/2}\log(2/δ))$, which is also sharp. This improvement is obtained by directly converting two-generator Stengle refutations into certificates for the original quadratic module. We also establish sharp degree bounds for trigonometric SOS certificates on tori. In particular, for the full torus without additional constraints, the optimal worst-case order improves to $δ^{-1/4}$, whereas additional equality constraints can lead the order to $δ^{-1/2}\log(2/δ)$. These results also yield sharp worst-case convergence rates for the Lasserre hierarchy.

Closest papers

Nearest neighbours by meaning across the whole index.

Hardness of Approximation for Polynomial Optimization over Sphere for Linear Programming Relaxation Hierarchy

cs.CC ·2026-11-06 ·Mrinalkanti Ghosh
theory similarity 0.66
Abstract

Semidefinite programming (SDP), particularly the sum-of-squares (SoS) hierarchy, provides $n^{O(q)}$-time approximation and certification algorithms for optimizing degree-$d$ homogeneous polynomials on the unit sphere. For arbitrary inputs, degree-$q$ SoS gives a powered-objective approximation factor $O_d((n/q)^{d/2-1})$ [BGGLT17]. For random order-$d$ tensors, degree-$d$ SoS has an integrality-gap lower bound of $2^{-O(d)}(n/d)^{d/4-1/2}$ relative to the true spherical maximum; lower bounds also extend to growing SoS degree in tensor PCA [BGL17,HKP17]. We establish lower bounds for weaker linear-programming relaxation hierarchies. Our degree-$q$ moment LPs impose the sphere identities and any prescribed, instance-independent family $\mathcal{G}$ of valid polynomial inequalities of degree at most $q$. They include Sherali--Adams-type product hierarchies. For every even $d\ge2$, constant $C>0$, and $q$ satisfying $2d | q$ and $2d\le q\le n$, every such relaxation with at most $n^{Cq}$ tests has instances $P$ satisfying \[ \frac{\mathrm{PowLP}_{q,\mathcal{G}}(P)}{\|P\|_\infty}\ge \frac{c_{d,C}}{\sqrt{q\log n}}\left(\frac nq\right)^{d/2-1/2}.\] Here $\|P\|_\infty$ is the maximum absolute value of the polynomial over the sphere and $\mathrm{PowLP}_{q,\mathcal{G}}(P)$ is the relaxed objective. The exponent $d/2-1/2$ improves the leading dependence on $d$ relative to the $d/4$-type exponents in prior random-tensor SoS lower bounds. Our LP hierarchies impose weaker positivity conditions than semidefinite moment relaxations. It leaves open whether analogous degree dependence can be achieved in lower bounds for SDP hierarchies.

0.25

Exact rational certificates and a Lean formalization of the eleven-variable Vasc inequality

cs.SC ·2026-10-09 ·Dakai Guo, Ruichen Qiu, Yichuan Cao, Ruyong Feng, Xiao-Shan Gao
theorycode/data similarity 0.63
Abstract

We prove that the cyclic sum $\sum_{i=0}^{10}(x_i-x_{i+1})/(x_{i+1}+x_{i+2})$ is nonnegative for every strictly positive real eleven-tuple, with indices taken modulo eleven. Clearing denominators reduces the problem to a homogeneous polynomial. Subtracting the smallest coordinate then separates the proof into nonnegativity of a common-translation derivative and nonnegativity on a full boundary face. We supply exact rational polynomial certificates in Gram-matrix form for both statements. The derivative certificate uses a linear multiplier, centered monomials and cyclic averaging; the boundary certificate uses a strictly positive quadratic multiplier and uncentered monomials. Their verification requires 6,069 cyclic coefficient comparisons and 34,304 literal coefficient comparisons. All 606 certificate matrices are certified by integer congruences with strictly diagonally dominant images. A Lean 4 development formally verifies the certificate checks and their connection to the original inequality. The exact certificate data, replay programs, and formal sources are publicly available.

0.20

Exact certification for conic optimization over quadratic modules: partitions of unity and recession directions

cs.SC math.OC ·2026-11-04 ·Didier Henrion, Alaa Ibrahim, Victor Magron
similarity 0.60
Abstract

We consider linear conic problems whose cone is a product of truncated quadratic modules, the sum-of-squares (SOS) side of the moment-SOS hierarchy. A floating-point solution is turned into an exact rational certificate in three steps: rounding, repair of each block residual by a constant, and absorption of the constants along a recession direction of the problem. The repair relies on strict partitions of unity in the quadratic modules. We characterize their existence, relate the canonical one to the analytic center of the dual pseudo-moment cone, Christoffel-Darboux polynomials and Pell equations, and we derive closed-form rational partitions for balls and boxes. The loss incurred by the certification is the optimal value of a recession problem, equal to a support function of the masses of the dual feasible pseudomoments. The method is illustrated on polynomial optimization, volume computation and positivity of polynomials along D-finite trajectories.

0.26

An Optimal Separation Between Certificate Complexity and Approximate Degree

cs.CC ·2026-08-31 ·Kaspars Balodis
theory similarity 0.60
Abstract · 17 pages

We prove that certificate complexity can be quartically larger than approximate degree. More precisely, we construct a family of total Boolean functions $G$ with $$ C(G) = \tildeΩ(\tilde{deg}(G)^4), $$ where $C$ denotes certificate complexity and $\tilde{deg}$ denotes $1/3$-approximate degree. This is optimal up to polylogarithmic factors, since every total Boolean function $f$ satisfies $C(f)\le O(\tilde{deg}(f)^4)$ by the classical block-sensitivity bounds of Nisan and Nisan--Szegedy. Thus the result closes the gap between these two measures and improves the previously best known separation $C(f)=\tildeΩ(\tilde{deg}(f)^3)$ by Balodis, Ben-David, Göös, Jain, and Kothari. The construction starts from the partial function they used to quadratically separate $0$-certificate complexity from unambiguous $1$-certificate complexity. It already has the required certificate hardness, but its $0$-certificates are unstructured, which blocks the derivation of a low-degree verifier. We keep its $1$-condition and restrict the $0$-inputs to those certified by a structured family whose validity admits a low-degree approximant, while preserving the quadratic hardness. The partial function with its low-degree verifier is then fed through the cheat-sheet framework to yield the total function $G$ with the claimed separation. The main technical ingredient is an approximate polynomial that verifies the certificate in degree $\tilde{O}(\sqrt n)$. The verifier forms a low-degree count $W$ of the candidate $1$-certificates that remain compatible with the asserted $0$-certificate, and tests whether this count is zero. Crucially, the construction ensures that $W$ never exceeds $\tilde{O}(n)$, instead of the $Θ(n^2)$ candidate pairs it counts bringing the verification down to degree $\tilde{O}(\sqrt n)$.

0.50

A Finite Certificate for the Positive $n=11$ Vasc Inequality

cs.SC ·2026-10-03 ·Tiancheng Xu, Wensheng Yu
theory similarity 0.60
Abstract

We establish the Vasc cyclic inequality for all strictly positive real eleven-tuples by a finite exact certificate. Cyclic rotation places a minimum at the first position, and rank words together with cumulative gaps reduce the problem to $10!=3{,}628{,}800$ homogeneous integer polynomials of degree eleven. Independent coefficient reconstruction proves $3{,}358{,}617$ roots directly. The remaining $270{,}183$ roots are covered by $267{,}952$ ordinary midpoint certificates, $2{,}195$ complete binary subdivision certificates, and $36$ complete certificates containing partial sorting nodes. Each nontrivial leaf is checked by subtracting weighted AM-GM midpoint circuits from a positive multiple of the transformed polynomial and verifying every residual coefficient. Explicit word-set comparisons certify disjointness and exact coverage. We prove the soundness of the leaves and both subdivision rules, then recover the rational inequality by positive denominator clearing and continuity. The resulting proof combines explicit mathematical reductions with independently checked exact integer certificates.

0.47

Block Sensitivity and Certificate Complexity of Rotation Symmetric Boolean Functions

cs.CC math.COcs.DM ·2026-10-12 ·Yuan Li, Jing Zhang
theory similarity 0.60
Abstract · Version 2, 44 pages

We investigate block sensitivity and certificate complexity of monomial rotation-symmetric Boolean functions, obtaining exact formulas and structural classifications for several families. For odd-degree monomial rotation-symmetric functions, the equality $s(f)=n$ established in our earlier work yields $bs(f)=C(f)=n$. For quadratic monomial rotation-symmetric functions, we determine both measures completely and prove that block sensitivity equals certificate complexity. For consecutive quartic monomials, we determine sensitivity, block sensitivity, and certificate complexity in every residue class of the number of variables. Our principal result is an exact global block-sensitivity formula for consecutive monomials of every even degree $d\ge4$. Writing $n=q(d+2)+ρ$, where $0\leρ<d+2$ and $q\ge\max\{2,d/2-1\}$, we prove \[ bs(F_{d,n})=n-\min\left\{\left\lceil\fracρ{2}\right\rceil,d+2-ρ\right\}. \] We also establish the corresponding sensitivity formula by a self-contained argument, yielding arbitrarily large gaps between sensitivity and block sensitivity as the degree varies. For certificate complexity, we obtain exact pointwise formulas for structured run-and-gap configurations and establish additional global equalities, including $C(F_{6,8q+5})=bs(F_{6,8q+5})=8q+2$ for $q\ge2$. Our methods combine cyclic run decomposition, parity arguments, explicit sensitive-block constructions, and constant-subcube certificates. The exact global certificate complexity for arbitrary even degrees remains open.

0.43

Majority and Torus Polynomials: Bounded-Lift Lower Bounds and Explicit Constructions

cs.CC ·2026-10-13 ·Saint Wesonga
similarity 0.58
Abstract

Bhrushundi et al. (2019) introduced torus polynomial approximation as an approach to separating Majority from $ACC^0$. In this model, approximation is measured modulo integers. Krishan and Vishwanathan (2026) developed a duality framework for lower bounds and posed five open problems. We resolve two of these, concerning integer lifts and explicit polynomial approximations. An integer lift records the integer shifts that turn a torus approximation into an ordinary real approximation. We show that a degree-d torus polynomial approximating Majority with error at most 1/8 and lift contained in an interval of width $B$ must satisfy $d(B + 1) = Ω(n)$. This rules out low-degree approximating polynomials with lifts in {-1, 0, 1}, answering their Open Problem 2. We also answer Open Problem 5 by giving, for every Boolean function on $n \geq 1$ variables, an explicit torus polynomial approximation of degree at most $n - 1$. Its error is optimal: zero when the accepting set has even cardinality and $2^{-n-1}$ otherwise. The results presented were discovered and formalized in Lean using GPT-6 Astra.

0.31

A new upper bound for $A(19,6,8)$

cs.IT math.CO ·2026-10-30 ·Jiang Chang
theory similarity 0.56
Abstract · 3 pages

We compute Polak's bound $A_4(19,6,8)$ for binary constant weight codes, obtaining the numerical value $673.04001$. An exact rational certificate gives $A_4(19,6,8)\le 673.0400143064802474039375132665301315202504$, and hence $A(19,6,8)\le 673$. This improves the upper bound $693$ listed in Brouwer's table. The certificate is verified by a separate program using exact rational arithmetic.

0.23