PaperlayerView exact revision on arXiv

Source-linked AI summary

Vanishing Ideals and the Computational Tractability of Sum-of-Squares over Boolean Domains

Monaldo Mastrolilli

arXiv:2609.37929v1cs.DS

TL;DR

Low-degree SoS proofs do not by themselves settle polynomial-time computation, because coefficient sizes and moment affine dependencies also matter. The paper makes truncated Boolean identities usable through controlled derivations and a constructible augmented moment body. For Min- and Max-closed systems, it gives polynomial-time proof search and exact-feasible moment optimization with a higher-level relaxation comparison.

  • Problem

    Low SoS degree alone does not guarantee polynomial-time computation: certificate coefficients may be too large, and identities can confine feasible moments to a proper affine subspace.

    Source: §1 · p. 3

  • Method

    The paper uses the complete truncated identity space both for controlled two-sided SoS derivations and for a constructible augmented moment relaxation with explicit rational geometric bounds.

    Source: §1 · pp. 3–4

  • Results

    Degree at most 8d + 4 suffices for polynomial-time rational proof search under a degree-2d proof promise, while the degree-2d pseudoexpectation is exactly feasible and ε-optimal for K2d.

    Source: §5.5 · pp. 24–25

  • Takeaways & Limitations

    For Min-closed systems, one structural analysis supplies both the computable identity space and its low-degree derivability; Max-closed systems follow by Boolean complementation.

    Source: §5.5 · p. 25

    A truncation below the degree of stored moments may miss required identities; for example, a degree-one basis misses x1x2 at moment degree two.

    Source: §4.2 · p. 18

Abstract

from arXiv · show

Building on the bit-complexity framework of Raghavendra-Weitz and the moment-SOS criteria of Gribling-Polak-Slot, we study the effective use of truncated vanishing identities over Boolean polynomial systems. A complete, constructible identity space gives an augmented moment SDP that can be optimized with exact rational feasibility and arbitrary additive accuracy. We give a self-contained geometric implementation: an explicit affine reduction and a simplex of Boolean evaluations supply the radius bounds required by rational ellipsoids. The identity space can be constructed directly or extracted from a supplied graded Groebner basis, including one supplied at a higher truncation degree. An explicit transfer theorem connects this augmented formulation to the original system. Two-sided SoS derivations eliminate the added equality axioms from certificates, with controlled degree and coefficient growth, and imply containment of a projected higher-level moment relaxation in the augmented body. Together with spectral coefficient bounds, this gives polynomial-time search for rational proofs with an additive perturbation. For Min-closed linear systems, propagation constructs the identity space in polynomial time at fixed degree and gives degree-(4t+4) certificates for both signs of each degree-t basis element. Consequently, a rational degree-(8d+4) proof of f + epsilon >= 0 can be found in polynomial time for fixed d whenever f >= 0 has a degree-2d proof. The augmented degree-2d moment SDP can be optimized in polynomial time with exact rational feasibility and a comparison to the original degree-(8d+4) relaxation. Boolean complementation gives the same results for Max-closed systems, including generalized packing and covering. Min-closed systems thus provide a concrete application of the general criteria. All complexity bounds are in the Turing model.

1 Introduction

Polynomial-time SoS computation requires more than low degree: coefficient sizes and affine dependencies among moments must also be controlled. The paper uses the complete space of truncated Boolean vanishing identities to connect proof search with exact-feasible moment optimization.

1 Introduction

  • Low SoS degree alone does not ensure polynomial-time computation: certificate coefficients may be too large, and moment constraints may force the feasible set into a proper affine subspace.The latter can leave the displayed moment coordinates with empty interior even when the relative interior is well behaved.Source: §1 · p. 3
  • The complete truncated identity space serves two distinct roles: controlled derivability supports proof search, while a constructible rational spanning list supports moment optimization.Two-sided derivations prove both b ≥0 and −b ≥0, allowing added identities to be used and later eliminated from certificates.Source: §1 · pp. 3–4
  • A degree-controlled transfer theorem eliminates added equations using two-sided SoS proofs, tracking the resulting degree and coefficient growth.If b has degree t and both signs have degree-Dt proofs, its use in a degree-2d certificate can be eliminated within degree Dt + 2(2d − t).Source: §1 · p. 4
  • Adding all identities through degree 2d gives an augmented moment body that can be optimized with exact rational feasibility and prescribed additive accuracy.The paper constructs affine coordinates, quantitative inner and outer radius bounds, and a strong rational separation oracle for the ellipsoid method.Source: §1 · pp. 4–5
  • The identity list can be constructed directly or extracted from a supplied reduced graded Gröbner basis of degree D ≥ 2d, including one supplied above degree 2d.Graded division recovers the required identities, and standard monomials give independent moment coordinates; both routes define the same body.Source: §1 · p. 5
  • When identities through degree 2d have two-sided derivations by an even degree κ ≥ 2d, the augmented body supports a comparison with the original degree-κ moment relaxation.For maximization, its pseudoexpectation has objective value at least the original relaxation's optimum, up to the requested additive error.Source: §1 · p. 5
  • For Min-closed systems, small-support closures construct the identities, while propagation yields degree-(4t+4) proofs for both signs of each degree-t basis element.The systems are rowwise Min-closed; generalized packing includes classical packing but may also have mixed-sign rows that are not downward-closed.Source: §1 · p. 5
  • For Min-closed systems, the application gives polynomial-time rational proof search in degree 8d + 4 and polynomial-time optimization of the augmented degree-2d moment body, returning an exactly feasible, ε-optimal pseudo-expectation.Boolean complementation yields corresponding results for Max-closed systems.Source: §1 · p. 6

2 Preliminaries and conventions

The preliminaries fix Boolean moment, degree, and encoding conventions used to state the algorithms. They also specify how certificates, vanishing identities, and rational separation are represented.

Preliminaries and conventions

  • The moment degree is 2d and the moment-matrix order is d; input encoding length counts dimensions and monomial supports, and complexity bounds count bit operations.Accuracy parameters are positive rationals, and logarithms are base two.Source: §2 · p. 7
  • A vector indexed by squarefree monomials defines a linear functional on polynomials of degree at most t, with x_∅ = 1.The functional assigns its coordinate indexed by T to the squarefree monomial x_T.Source: §2 · p. 7
  • The original degree-t relaxation uses truncated constraints; a constraint above degree t has no block or multiplier at that truncation but still defines the feasible set.Degrees are measured by ordinary total degree before multilinearization.Source: §2 · p. 7
  • SoS certificates are encoded by positive-semidefinite Gram matrices and equality-multiplier coefficients, and Boolean reduction preserves degree.A rational positive-semidefinite Gram matrix is an exact rational certificate even when a square-root factorization has irrational entries.Source: §2 · pp. 7–8
  • A degree-r identity list is complete when its rational span equals the degree-at-most-r vanishing polynomials; a truncated Gröbner basis alone may need admissible monomial multiples.The identities are defined by vanishing on every Boolean feasible point.Source: §2 · pp. 7–8

3 The dual criterion: controlling certificates through vanishing identities

The dual criterion turns low-degree proofs into bounded-coefficient proofs by controlling truncated vanishing identities and eliminating added equality axioms. Under its hypotheses, it supports polynomial-time search for rational proofs with an additive perturbation and yields a comparison with a higher-level moment relaxation.

3 The dual criterion: controlling certificates through vanishing identities

  • Graded division and transfer eliminate the vanishing residual after a bounded representation is obtained, completing the dual-criterion argument.The bounded-certificate lemma's spectral estimates apply to rational Boolean evaluation moments, including when inequalities vanish at feasible points.Source: §3 · pp. 8, 11
  • Projecting away Gram components that vanish on feasible points yields an equivalent proof representation with polynomially bounded Gram entries and residual coefficients.The bounded representation is an existence argument; the search need not construct the projected matrices or enumerate the feasible set.Source: §3 · pp. 8–9
  • Two-sided SoS proofs of added identities let substitution eliminate their equality axioms, controlling the transferred certificate's degree and coefficient growth.Rational input certificates yield rational outputs through explicit polynomial-bit-time substitution.Source: §3 · pp. 9–10
  • The same two-sided derivations imply that a projected higher-degree moment relaxation lies inside the augmented body defined by vanishing identities.When admissible multiples span the full truncated identity space, their moment equalities define that body.Source: §3 · p. 10
  • Both signs of each truncated basis element having degree-O(d) proofs with bounded coefficients lets degree-2d proofs become controlled-coefficient proofs of degree O(d), searchable as rational proofs of f + ε ≥ 0.The search is polynomial time under the stated promise that a degree-2d proof of f ≥ 0 exists.Source: §3 · p. 11
  • A computable coefficient bound enables rational certificate search with polynomial cost, using a relaxed coefficient SDP and Boolean residual repair.The search uses the original coefficient equations and bound, not the basis or its two-sided proofs.Source: §3 · p. 11

4 The primal criterion: identities determine the right geometry

These sections show how a complete truncated space of vanishing identities determines the affine geometry of an augmented moment body, which can be optimized with exact rational feasibility and additive accuracy. They describe constructing or extracting the identities and using two-sided SoS derivations to compare the augmented body with higher-level moment relaxations.

4.1 Proof of the primal criterion

  • The complete identities determine the affine hull; Boolean evaluations provide a simplex with a controlled inner radius, while moment bounds and exact PSD tests give outer bounds and rational separation for ellipsoid optimization.This self-contained construction needs the numerical radius, but not the simplex vertices or centre.Source: §4 · p. 12, §4.1 · pp. 14–15

4 The primal criterion: identities determine the right geometry

  • Given a constructible rational spanning list of degree-2d vanishing identities, the primal criterion computes a rational feasible point within ε of the augmented body's optimum in polynomial time, with all constraints satisfied exactly.For fixed d and ε = 2^-s, the running time and output length are polynomial in the input length and s + 1.Source: §4 · p. 12, §4.1 · p. 15

4.1 Proof of the primal criterion

  • When each identity and its negative has an original-system SoS proof of degree at most κ, projecting the degree-κ moment relaxation into degree 2d yields a subset of the augmented body, enabling objective comparison but not equality.The augmented body is optimized at moment degree 2d; the projection inclusion does not imply that its points extend to the higher-level relaxation.Source: §4 · p. 12, §4.1 · pp. 15–16

4.2 Two effective routes to the same affine hull

  • The identity space can be constructed directly or extracted by graded division from a supplied correct reduced graded-basis truncation of any degree D ≥ r, yielding the same augmented moment body at degree r.The extracted identities span the vanishing ideal through degree r, and adding them as equality axioms gives exactly that body's moment formulation.Source: §4.2 · pp. 16–17
  • From the supplied graded basis, normal forms provide rational affine coordinates and a rational point within ε of the augmented body's optimum in time polynomial in the system, basis, objective, and ε encodings.The moment degree remains r even when the supplied truncation has degree D > r, and degree-r feasibility conditions hold exactly.Source: §4.2 · p. 17
  • For arbitrary real values assigned to the standard moments, with the constant moment set to one, the construction yields a vector in H_r, and every vector in H_r is reconstructed from those moments.The parametrization has no remaining affine dependencies among these p coordinates; PSD feasibility is imposed after parametrization.Source: §4.2 · p. 18
  • The target moment degree r, available graded-basis degree D, and SoS proof bound κ serve distinct roles: r sets the moment variables, D supplies basis data, and κ controls the level comparison.Elements of degree above r are discarded; if the basis is computed rather than supplied, its computation cost must also be counted.Source: §4.2 · p. 18
  • A degree-d truncated basis can miss identities needed by a degree-2d moment body: for x1 + x2 ≤ 1, x1x2 vanishes although no nonzero degree-one identity exists.The relevant truncation degree is the degree of all stored moments, not merely the order of the moment matrix.Source: §4.2 · p. 18

4.3 SoS derivability supplies the higher-level comparison

  • If both signs of each degree-2d basis identity have degree-κ proofs, then π2d(Sκ) ⊆ K2d; when Db = O(d), this gives Theorem 4.1’s comparison.The identity list must be complete at degree 2d, and the comparison follows from the bounded two-sided derivations.Source: §4.3 · pp. 18–19
  • The same identity space determines moment geometry and supports proof search through bounded two-sided certificates; Min-closed systems provide both ingredients through closures.Admissible basis multiples span the identity space, and two-sided proofs let the added equality axioms be used in certificates and moment constraints.Source: §4.3 · p. 19

5 Application to Min-closed and Max-closed systems

This section develops closure-based identity and SoS methods for Min-closed Boolean systems, yielding polynomial-time proof search and moment optimization, and transfers these results by Boolean complementation to Max-closed systems and generalized covering counterparts. For maximization applications, the additive objective guarantee does not by itself establish an approximation ratio.

5.1 Construct the full list Q2d by closures

  • For each T, propagation computes its least feasible support extension, and the resulting closure polynomials span all degree-at-most-2d vanishing identities in polynomial time.The closure algorithm also detects infeasibility by returning ⊥ for cl(∅).Source: §5.1 · p. 20

5.2 Comparing the direct and Gröbner-basis routes

  • The direct closure list and reduced graded basis are constructible in polynomial time and yield the same augmented moment body at degree 2d.A supplied basis of higher degree can be filtered to the target degree; degree 8d+4 is for the later comparison, not the primal construction.Source: §5.2 · pp. 21–22

5.3 Propagation and infeasibility have degree-four certificates

  • Propagation proves every forced xi = 1 assertion and refutes infeasible systems with rational degree-four Gram SoS proofs of polynomial bit complexity.The degree-four bound is preserved across the entire propagation chain.Source: §5.3 · pp. 22–23

5.4 The reduced basis and its two-sided certificates

  • Both signs of every degree-t element of the reduced graded vanishing-ideal basis have rational Gram SoS proofs of degree at most 4t+4, with polynomial coefficient bit lengths.The theorem applies to rowwise Min-closed systems.Source: §5.4 · p. 24

5.5 Both algorithmic conclusions and the exact degree accounting

  • Given a degree-2d SoS proof of f ≥ 0, polynomial-time search finds a rational f+ε ≥ 0 proof of degree 8d+4, while degree-2d moments optimize against the original degree-(8d+4) relaxation.The degree-2d moment constraints hold exactly, and the objective is within ε of the maximum at level 8d+4.Source: §5.5 · pp. 24–25

5.6 Max-closed systems via Boolean complementation

  • Boolean complementation transfers the Min-closed algorithmic conclusions to rowwise Max-closed systems while preserving certificate degree, rational feasibility, objective values, and hierarchy inclusion.The transformation has polynomial encoding cost.Source: §5.6 · p. 25
  • Boolean complementation gives a rational affine bijection between the original and transformed degree-r moment relaxations and augmented bodies, preserving evaluations and objectives.The map is invertible and commutes with restriction to lower degree.Source: §5.6 · p. 26

5.7 Generalized packing and covering

  • Min-closed rows define generalized packing and Max-closed rows generalized covering; complementation transfers the algorithmic results, and classical packing and covering are special cases.The closure promises apply to each row on the Boolean cube, including mixed-sign rows that individually satisfy the relevant promise.Source: §5.7 · p. 26
  • For maximization applications using degree-2d pseudoexpectation inequalities, Corollary 5.8 supplies them exactly and guarantees an objective at least the true Boolean optimum minus ε.An application-specific approximation ratio still requires a rounding theorem and conversion of the additive error to the required scale.Source: §5.7 · p. 26

Declaration on the use of AI tools

The author states that AI tools assisted with editing, proof drafting, and checks, while taking full responsibility for the final content.

Declaration on the use of AI tools

A Algebraic tools and coefficient bounds

The appendix establishes quantitative algebraic tools for Boolean systems, including degree-preserving reductions and bounds needed for rational certificate construction.

A Algebraic tools and coefficient bounds

  • Boolean reduction represents p − ml(p) using Boolean equations without increasing degree, with polynomial-time computation and coefficient bit length for rational input.The multilinearization also satisfies ∥ml(p)∥1 ≤ ∥p∥1.Source: A Algebraic tools and coefficient bounds · p. 28
  • For q in the ideal with degree at most r, graded division gives a representation with degree at most r and an explicit coefficient-size bound.For rational data, division takes polynomial bit time in the truncated basis and polynomial lengths.Source: A Algebraic tools and coefficient bounds · p. 29
  • Every positive eigenvalue of an integer positive semidefinite matrix of order t with entries bounded by U is at least (tU)^−t.The bound follows by combining the integer determinant coefficient lower bound with an upper bound on the eigenvalues.Source: A Algebraic tools and coefficient bounds · p. 29
  • For even t and ε ≥ ∥ml(e)∥1, ε + e has a rational Gram SoS certificate from Boolean equations of degree at most t.The certificate is constructible in polynomial bit time in the degree-t monomial count and the encodings of e and ε.Source: A Algebraic tools and coefficient bounds · p. 29

A.1 A bit bound for a supplied Boolean basis

The appendix bounds the encoding size of a supplied Boolean basis and characterizes reduced graded bases for Min-closed Boolean sets.

A.1 A bit bound for a supplied Boolean basis

  • A supplied reduced graded basis truncation has rational coefficients with O(N_r log(N_r + 1)) bits and total encoding length polynomial in W_r.This is a size bound, not an algorithm for constructing the basis.Source: §A.1 · p. 30

A.2 Reduced bases for Min-closed Boolean sets

  • For a nonempty Min-closed Boolean set, each reduced graded lexicographic basis element is a squarefree monomial, a difference of squarefree monomials, or a Boolean polynomial x_i^2 − x_i.Source: §A.2 · p. 30
  • The standard monomials are the least monomials in the nonzero evaluation classes, and every nonchosen monomial yields an identity with that class representative or zero.Independence of the feasible-support indicator functions identifies the standard monomials and determines the basis tails.Source: §A.2 · pp. 30–31

B Rational linear algebra and Boolean moment geometry

This appendix supplies bit-complexity and geometric bounds for the primal moment-SDP algorithm. It establishes polynomial-time rational elimination, a uniform ball inside an integral Boolean simplex, and boundedness of Boolean moment sets.

Rational linear algebra and Boolean moment geometry

  • The appendix gives direct proofs of the polynomial bit bounds, simplex radius, Boolean moment bounds, and rational negative-witness guarantees used by the primal algorithm.These bounds apply to the free-coordinate formulation of the moment SDP.Source: B Rational linear algebra and Boolean… · p. 31

Rational linear algebra

  • Polynomial-bit rational elimination solves, rank-tests, and parametrizes linear systems, with free variables chosen among the original coordinates.The appendix also gives an exact rational PSD test that either certifies positivity or returns a polynomial-length negative witness.Source: B Rational linear algebra and Boolean… · pp. 31–33

Boolean moment geometry

  • A simplex with affinely independent 0/1 vertices has a uniform inner-ball radius computable from its dimension in polynomial time.The resulting closed ball lies inside the simplex, and the radius has logarithm O(p log(p + 1)).Source: B Rational linear algebra and Boolean… · pp. 31–32
  • Every degree-2d Boolean pseudo-moment has absolute value at most one, and the selected-moment set is compact and convex.Its boundedness follows from the Boolean moment bounds, while it is nonempty because it contains every Boolean evaluation vector.Source: B Rational linear algebra and Boolean… · p. 32

C The ellipsoid method and exact-feasible optimization

This appendix records the rational central-cut ellipsoid theorem and proves the exact-feasible optimization consequence used in the paper. It also establishes the reductions and radius-dependent complexity estimates needed for that argument.

The ellipsoid method and exact-feasible optimization

  • The appendix uses the classical GLS rational central-cut ellipsoid theorem and gives its statement, accepted-point convention, and reference.The theorem itself is identified as an external algorithmic result; subsequent reductions and radius-dependent complexity estimates are proved in the appendix.Source: C The ellipsoid method and… · p. 33
  • The appendix proves the exact-feasible optimization consequence used in the paper.The argument remains valid when the center of the inner ball is not supplied.Source: C The ellipsoid method and… · p. 33
  • The complexity discussion uses ambient dimension p, oracle-instance length len, requested accuracy τ, and the Turing bit model.The parameter conventions are stated for the appendix's ellipsoid argument.Source: C The ellipsoid method and… · p. 33

C.1 Preliminaries and the GLS ellipsoid theorem

The preliminaries specify rational encodings and complexity parameters for the ellipsoid theorem. They normalize radius and accuracy bounds to powers of two and account for processing the encoded inputs.

Preliminaries and the GLS ellipsoid theorem

  • The ellipsoid setup uses supplied bounds R = 2^k1, ρ = 2^-k2, and τ = 2^-k3, with integer exponents encoded in binary.Arbitrary positive rational bounds can be replaced by suitable powers of two without losing geometric validity or requested accuracy.Source: §C.1 · p. 34
  • Runtime bounds include the time to read and process arbitrarily encoded rational inputs, and the requested accuracy may be replaced by a no-larger rational value.The appendix measures arithmetic in the Turing bit model and defines oracle-polynomial time using query lengths and bit operations.Source: §C.1 · p. 34
  • The GLS theorem is stated for a closed convex set contained in a rational radius-R ball and uses a rational separation-oracle query point and tolerance.The oracle either accepts within the stated tolerance or returns a normalized rational separating vector.Source: §C.1 · p. 34

There is an oracle-polynomial rational algorithm returning either

The rational ellipsoid procedure returns an accepted point or a small enclosing ellipsoid. With a strong rational separation oracle, it yields an exact point in the set or an ellipsoid of volume at most ν.

There is an oracle-polynomial rational algorithm returning either

  • The theorem’s accepted-point clause permits a queried center in C + ν to be returned as an accepted point.The theorem is stated in the appendix as a restatement of GLS, with its rational implementation and iteration bound referenced there.Source: There is an oracle-polynomial rational… · pp. 34–35
  • A strong rational separation oracle gives a rational point in C or an ellipsoid containing C with volume at most ν.If vol(C) > ν, the ellipsoid alternative is excluded, so the algorithm must return a point in C.Source: There is an oracle-polynomial rational… · p. 35
  • The returned point is exactly in C because the adapter accepts only points certified by the strong oracle.The ellipsoid alternative provides a volume upper bound, including when C is nonempty but has small volume.Source: There is an oracle-polynomial rational… · p. 35

C.2 An explicit ball of nearly optimal points

A convex body containing an inner ball has a ball of nearly optimal points for any linear objective. A rational volume threshold lower-bounds the volume of any convex set containing a specified-radius ball.

C.2 An explicit ball of nearly optimal points

  • The near-optimal-ball guarantee assumes compact convex K, an inner ball B(a, ρ), an outer bound K ⊆ B(0, R), and R ≥ 1.The objective vector c and accuracy parameter η determine the construction; the center a and optimizer x* need not be known to the algorithm.Source: §C.2 · pp. 35–36
  • The ball centered at (1 − α)x* + αa with radius αρ lies in K and has objective value at least OPT − η/2 throughout.Here x* maximizes the objective over K, and a and ρ specify an included ball B(a, ρ).Source: §C.2 · pp. 35–36
  • For 0 < q ≤ 1, every convex set in R^p containing a radius-q ball has volume greater than ν(q), with 0 < ν(q) < 1.The rational threshold construction avoids computing the volume of the Euclidean unit ball.Source: §C.2 · p. 36

C.3 Exact-feasible approximate optimization

The appendix gives a rational-oracle procedure for approximate linear optimization that returns an exactly feasible rational point. Its running time is polynomial in the stated dimension, oracle, radius, objective, and accuracy parameters.

C.3 Exact-feasible approximate optimization

  • The procedure returns y ∈ K ∩ Q^p with the requested approximate-optimization guarantee, without requiring the inner-ball center a as input.It assumes K has a polynomial-time strong rational separation oracle and uses supplied rational radius bounds.Source: §C.3 · pp. 36–37
  • The running time is polynomial in p, len, 1 + log R, 1 + log(1/ρ), ⟨c⟩, and 1 + log(1/τ).For arbitrary positive rational bounds and accuracy, normalization and input encoding lengths are included.Source: §C.3 · p. 37
  • Threshold queries use Kβ = {x ∈ K : c⊤x ≥ β}; a low-volume outcome cannot occur when β ≤ OPT − η.The procedure need not decide whether Kβ is empty.Source: §C.3 · p. 37
  • A midpoint search retains an accepted feasible point while narrowing objective bounds until their width is at most τ.Success replaces the lower bound and retained point; failure decreases the upper bound, and termination yields the approximate result.Source: §C.3 · pp. 37–38
  • Threshold endpoint encodings grow by only O(1 + log(M + 1) + log D0 + j) after j queries, yielding polynomial bit work and output length.The total running-time claim combines this bound with polynomial bit work per oracle call.Source: §C.3 · p. 38

D Bounded-certificate search and residual repair

Bounded-certificate search perturbs a coefficient SDP to obtain an exactly feasible rational point, then repairs its residual with Boolean axioms. This yields a rational proof of a positively perturbed polynomial with polynomial encoding length.

D Bounded-certificate search and residual repair

  • A degree-t real Gram proof with bounded entries yields a rational degree-t Gram proof of a positively perturbed target in polynomial time.The input is a rational Boolean polynomial system and a supplied rational bound B on Gram entries and equality-multiplier coefficients.Source: D Bounded-certificate search and… · p. 39
  • The search constrains coefficient residuals to η, bounds variables by 2B, and shifts Gram blocks by ηI to make the SDP full-dimensional.The set Cη combines box bounds, approximate coefficient equations, and positive-semidefinite shifted Gram blocks.Source: D Bounded-certificate search and… · p. 39
  • A strong rational separation oracle and the radius bounds produce an exactly feasible rational point in Cη without supplying its center.The construction uses rational separators for box and coefficient constraints and a rational negative witness for a failed PSD condition.Source: D Bounded-certificate search and… · p. 39
  • Shifting each Gram block by ηI gives an exact rational SoS proof of P ≥ 0, after which Boolean correction certifies ε + e ≥ 0 at degree t.Adding the correction certificate to P gives the exact identity for f + ε, with final matrix and coefficient lengths polynomially bounded.Source: D Bounded-certificate search and… · pp. 39–40
Loading 2609.37929v1…