Sums of squares on the hypercube

DOI10.1007/S00209-016-1644-7zbMATH Open1375.14187arXiv1402.4199OpenAlexW1541730833MaRDI QIDQ329957FDOQ329957

Authors: Grigoriy Blekherman, João Gouveia, James Pfeiffer 

Publication date: 24 October 2016

Published in: Mathematische Zeitschrift (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1402.4199

Recommendations

• FSTTCS 2004: Foundations of Software Technology and Theoretical Computer Science
• Sums of squares of polynomials with rational coefficients
• Symmetric sums of squares over \(k\)-subset hypercubes
• scientific article; zbMATH DE number 1601019
• On Hilbert's 17th problem in low degree

Mathematics Subject Classification ID

Queues and service in operations research (90B22) Real algebraic sets (14P05) Hilbert-Samuel and Hilbert-Kunz functions; Poincaré series (13D40) Effectivity, complexity and computational aspects of algebraic geometry (14Q20) Representations of finite symmetric groups (20C30)

Cites Work

• Global optimization with polynomials and the problem of moments
• Title not available (Why is that?)
• Title not available (Why is that?)
• Semidefinite programming relaxations for semialgebraic problems
• Title not available (Why is that?)
• An explicit equivalent positive semidefinite program for nonlinear 0-1 programs
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite representations for finite varieties
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Positive polynomials and sums of squares
• Cayley-Bacharach theorems and conjectures
• Theta bodies for polynomial ideals
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Title not available (Why is that?)
• Title not available (Why is that?)
• 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
• Certificates of impossibility of Hilbert-Artin representations of a given degree for definite polynomials and functions
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope

Cited In (19)

• Title not available (Why is that?)
• Sums of squares of polynomials with rational coefficients
• Title not available (Why is that?)
• Union of hypercubes and 3D Minkowski sums with random sizes
• Symmetric sums of squares over \(k\)-subset hypercubes
• Positivity certificates and polynomial optimization on non-compact semialgebraic sets
• On vanishing sums of roots of unity in polynomial calculus and sum-of-squares
• Sharp degree bounds for sum-of-squares certificates on projective curves
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem
• Query complexity in expectation
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Error bounds for polynomial optimization over the hypercube using Putinar type representations
• Breaking symmetries to rescue sum of squares in the case of makespan scheduling
• Harmonic Hierarchies for Polynomial Optimization
• Title not available (Why is that?)
• Computing sparse Fourier sum of squares on finite abelian groups in quasi-linear time
• Sum-of-squares hierarchy lower bounds for symmetric formulations
• On sumfree subsets of hypercubes

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)