CS Paper Radar

The Moment Method for Computing Real Points of Sparse Polynomial Systems

Tom Baumbach, Matías Bender

cs.SC math.ACmath.AG ·submitted 2026-09-27 07:26 UTC · v1
theory

Abstract

One of the most important problems in computational algebra is the computation of real solutions of a polynomial system. Lasserre, Laurent, and Rostalski introduced a numerical method to compute the real radical of an ideal defining a finite set of real points. Their method is based on moment matrices and reduces the problem to solving a semidefinite program. In this work, we build on this method and on the work of Laurent and Mourrain to exploit the sparsity of the input polynomials. For this purpose, we extend the theory of moment matrices to the setting of affine toric varieties. We prove that, for sparse polynomial systems, this approach allows us to recover real points on affine toric varieties. Moreover, we show that a projection of the spectrahedron associated with the semidefinite program is, in fact, a polytope, and we propose a variation of the method to compute only one real solution of the system.

Closest papers

Nearest neighbours by meaning across the whole index.

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

cs.DS ·2026-09-29 ·Monaldo Mastrolilli
theory similarity 0.60
Abstract

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.

0.42

Algebraic Expressivity Certificates for Shallow Polynomial Neural Networks

cs.LG math.ACmath.AG ·2026-09-11 ·Sepehr Akbari, Shahrzad Jamshidi
similarity 0.57
Abstract · 9 pages, 1 figure

We study exact representability by bias-free shallow polynomial neural networks using algebraic geometry. Over $\mathbb{C}$, a width-$r$ network with activation $z\mapsto z^d$ computes a sum of $r$ $d$-th powers of linear forms, whose Zariski closure is a Veronese secant variety. Ideal elimination therefore yields polynomial certificates of nonrepresentability. We implement this construction as a generic architecture-to-certificate pipeline. For quadratics, we recover the exact symmetric determinantal description and explain its dimension through orthogonal symmetry. In higher degree, the implementation recovers classical catalecticant and secant equations and maps the practical reach of direct elimination across a finite architecture sweep. We also derive the exact population loss floor for a rank-two quadratic network on the sphere, illustrating how an algebraic obstruction induces irreducible approximation error.

0.22

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

On computing the determinant over a ring

cs.SC cs.CC ·2026-11-05 ·Gilles Villard
similarity 0.52
Abstract

An algorithm is presented for computing the determinant and the characteristic polynomial of a matrix $A$ over an arbitrary commutative ring R. The algorithm uses $O(n^ω)$ ring additions, subtractions and multiplications, where $ω>2$ is a feasible exponent for matrix multiplication, that is, such that two $n\times n$ matrices over R can be multiplied using $O(n^ω)$ ring operations. The algorithm involves no division and no zero test, and its control depends only on $n$: for each $n$ it is a straight-line program. The approach combines a polynomial matrix point of view and a block Krylov point of view on the characteristic polynomial, which makes Strassen's elimination of divisions efficient. A bivariate matrix $λI-L(t)$, obtained from $A$ by a homotopy, is compressed in $\log n$ steps, each of which halves the dimension while only doubling the degree in $λ$. The cost of the homotopy is controlled by truncating the power series in $t$ at an order that only grows with the compression steps, from a constant to $n$.

0.22

Recovering Lower-Dimensional Semialgebraic Support of a Measure from its Moments

cs.LG math.STmath.OC ·2026-09-27 ·Ruben Karapetyan, Shenyuan Ma, Ales Wodecki, Jakub Marecek
similarity 0.51
Abstract

Recovering probability measures from their moments has numerous applications, esp. in connection with the method of moments in statistics and optimization. In the setting where measure need not be finitely atomic, but its support is known to be compact and semialgebraic with codimension at least one, the problem is still open. We combine moment-matrix kernel information with the Christoffel--Darboux kernel to provide a discrete approximation of the support. To validate the proposed approach, we test our algorithm on analytically computed moments and pseudo-moments arising from polynomial optimization problems without unique global minimizers. This complements well-known recent work on recovery of measures with algebraic support, where the kernel of a moment matrix can reveal polynomials vanishing on the support, and on recovery of sufficiently regular full-dimensional supports, where estimators constructed by thresholding the Christoffel--Darboux kernel are known to converge asymptotically to the support.

0.27

The sum-of-squares complexity of linear-algebraic principles

cs.CC ·2026-11-03 ·Dmitriy Kunisky, Xifan Yu
similarity 0.51
Abstract · 41 pages

We study the degree needed for sum-of-squares (SoS) proofs of several basic principles of real linear algebra. For any $n\times n$ matrix $A$ of rank greater than $r$, the Weak Rank Principle states that the equations $XY^\top=A$ with $n\times r$ matrix variables $X, Y$ have no solution. We show that this principle requires degree exactly $2r+2$ to prove. On the other hand, for $A=I_n$, setting $X = Y$ gives the Tight Frame Principle, which has a degree-$4$ proof. For $n\times n$ matrices, proving that a right inverse is also a left inverse requires degree exactly $2n+2$, while proving that orthonormal rows imply orthonormal columns again has a degree-4 proof. Using our lower bounds, we also derive related SoS degree lower bounds for polynomial systems encoding sign rank, matrix rigidity, small-width homogeneous non-commutative algebraic branching programs, and tensor CP rank. Lastly, we show that quantitative bounds on the Frobenius norms of the factors in the Weak Rank Principle can lower the degree required to refute $XY^\top=I_n$, but sufficiently large bounds still preserve the exact degree $2r+2$ from the unbounded case, giving a quantitative version of the Archimedean property arising in classical results on SoS proofs.

0.28

Refined complexity bounds for rational reconstruction and XGCD through Padé approximants and Cauchy interpolants

cs.SC ·2026-09-17 ·Vincent Neiger, Mohab Safey El Din, Kevin Tran
similarity 0.51
Abstract

When computing with univariate polynomials, two fundamental and related problems are the XGCD and rational reconstruction, classically solved in quasi-linear complexity using the half-gcd algorithm. These problems have various applications in algebraic computations and bear strong connections to linearly recurrent sequences, structured matrices, and continued fractions. This article first gives a collection of algorithmic reductions, showing that rational reconstruction and XGCD can be solved via the computation of bases of relations modulo a freely-chosen polynomial $M(x)$. In particular, one recovers the folklore idea that bases of Padé approximants (i.e., $M(x) = x^d$) can be used to perform quasi-linear rational reconstruction or XGCD, extending to fast algorithms the well-known link between the Berlekamp-Massey algorithm and the extended Euclidean algorithm. One highlight of these reductions is that, instead of approximants, one may rely on Cauchy interpolants (i.e., $M(x)$ vanishes at chosen points). In a second part, this article describes divide-and-conquer algorithms for approximants and interpolants along with complexity analyses showing an explicit leading constant in front of the dominant term. For interpolants, the best leading constant is obtained through a variant that stores polynomials represented by evaluations, and exploits fast extrapolation in order to avoid repeated conversions to the monomial basis; this requires special points, in geometric or arithmetic progression, or FFT points when the base field allows them. Combining the analyses with the reductions leads to the best complexity bounds we are aware of for rational reconstruction and XGCD. Perhaps surprisingly, even Padé approximants or Berlekamp-Massey-like computations, which intrinsically involve $M(x) = x^d$, are accelerated by reducing them to Cauchy interpolation at well-chosen points.

0.26

Approximate Polynomial Satisfiability is in the Counting Hierarchy

cs.CC ·2026-09-30 ·Nikhil Balaji, Mahsa Shirmohammadi, Sébastien Tavenas, James Worrell
theory similarity 0.50
Abstract

The Approximate polynomial satisfiability problem (APS), introduced by Guo, Saxena, and Sinhababu (CCC 2018), asks whether the zero vector lies in the Zariski closure of the image of a given polynomial map. Specifically, for a field $k$ with algebraic closure~$K$, the problem asks whether $\boldsymbol 0 \in\overline{\boldsymbol f(K^n)}$ for a polynomial map $\boldsymbol f=(f_1,\ldots,f_m)$ with $f_i\in k[X_1,\ldots,X_n]$. APS is a natural topological analogue of Hilbert's Nullstellensatz, namely the question of whether a given system of polynomial equations has a common zero. APS captures several problems in algebraic complexity, including border rank, hitting sets for border classes, and null-cone membership; it is known to be NP-hard and in PSPACE. We show that APS lies in the Counting Hierarchy (CH) over both the rationals and finite fields, substantially improving the known PSPACE upper bound. Our proof builds on a recent breakthrough due to Andrews, Garg, and Schost (FOCS 2026) on deciding Hilbert's Nullstellensatz in CH. As a corollary, our result improves the complexity of certifying hitting sets for border classes from PSPACE to CH. We also give a polynomial-time reduction of Hilbert's Nullstellensatz to APS, valid in any characteristic. In characteristic zero, we give a reduction of APS to the decision problem for the existential theory of real closed fields. Overall, our results place approximate polynomial satisfiability closer in complexity to exact polynomial feasibility and as a byproduct give improved complexity bounds for several problems arising in approximative complexity.

0.53