Sums of squares on the hypercube
From MaRDI portal
Abstract: Let X be a finite set of points in R^n. A polynomial p nonnegative on X can be written as a sum of squares of rational functions modulo the vanishing ideal I(X). From the point of view of applications, such as polynomial optimization, we are interested in rational function representations of small degree. We derive a general upper bound in terms of the Hilbert function of X, and we show that this upper bound is tight for the case of quadratic functions on the hypercube C={0,1}^n, a very well studied case in combinatorial optimization. Using the lower bounds for C we construct a family of globally nonnegative quartic polynomials, which are not sums of squares of rational functions of small degree. To our knowledge this is the first construction for Hilbert's 17th problem of a family of polynomials of bounded degree which need increasing degrees in rational function representations as the number of variables n goes to infinity. We note that representation theory of the symmetric group S_n play a crucial role in our proofs of the lower bounds.
Recommendations
Cites work
- scientific article; zbMATH DE number 1601019 (Why is no real title available?)
- scientific article; zbMATH DE number 1601795 (Why is no real title available?)
- scientific article; zbMATH DE number 4160796 (Why is no real title available?)
- scientific article; zbMATH DE number 177492 (Why is no real title available?)
- scientific article; zbMATH DE number 704831 (Why is no real title available?)
- A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
- Cayley-Bacharach theorems and conjectures
- Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
- Global optimization with polynomials and the problem of moments
- Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
- Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
- Positive polynomials and sums of squares
- Semidefinite Optimization and Convex Algebraic Geometry
- Semidefinite programming relaxations for semialgebraic problems
- Semidefinite representations for finite varieties
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Theta bodies for polynomial ideals
Cited in
(17)- Sharp degree bounds for sum-of-squares certificates on projective curves
- On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
- Harmonic Hierarchies for Polynomial Optimization
- Union of hypercubes and 3D Minkowski sums with random sizes
- scientific article; zbMATH DE number 6093164 (Why is no real title available?)
- Symmetric sums of squares over \(k\)-subset hypercubes
- An elementary recursive bound for effective Positivstellensatz and Hilbert's 17th problem
- Query complexity in expectation
- scientific article; zbMATH DE number 1757257 (Why is no real title available?)
- Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
- Error bounds for polynomial optimization over the hypercube using Putinar type representations
- On sumfree subsets of hypercubes
- Sparse sums of squares on finite abelian groups and improved semidefinite lifts
- Positivity certificates and polynomial optimization on non-compact semialgebraic sets
- The Spectrum of the Grigoriev–Laurent Pseudomoments
- Sums of squares of polynomials with rational coefficients
- Sum of squares lower bounds from symmetry and a good story
This page was built for publication: Sums of squares on the hypercube
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q329957)
