Sums of squares on the hypercube

DOI10.1007/s00209-016-1644-7zbMath1375.14187arXiv1402.4199OpenAlexW1541730833MaRDI QIDQ329957

João Gouveia, James Pfeiffer, Grigoriy Blekherman

Publication date: 24 October 2016

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

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

Mathematics Subject Classification ID

Representations of finite symmetric groups (20C30) 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)

Related Items (13)

Query Complexity in Expectation ⋮ Positivity certificates and polynomial optimization on non-compact semialgebraic sets ⋮ Sparse sums of squares on finite abelian groups and improved semidefinite lifts ⋮ Sum-of-squares hierarchy lower bounds for symmetric formulations ⋮ An Elementary Recursive Bound for Effective Positivstellensatz and Hilbert’s 17th problem ⋮ Breaking symmetries to rescue sum of squares in the case of makespan scheduling ⋮ On vanishing sums of roots of unity in polynomial calculus and sum-of-squares ⋮ The Spectrum of the Grigoriev–Laurent Pseudomoments ⋮ Harmonic Hierarchies for Polynomial Optimization ⋮ Symmetric sums of squares over \(k\)-subset hypercubes ⋮ Sharp degree bounds for sum-of-squares certificates on projective curves ⋮ Unnamed Item ⋮ Sums of squares of polynomials with rational coefficients

Cites Work

• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs
• Semidefinite representations for finite varieties
• Semidefinite programming relaxations for semialgebraic problems
• Global Optimization with Polynomials and the Problem of Moments
• An Explicit Equivalent Positive Semidefinite Program for Nonlinear 0-1 Programs
• Theta Bodies for Polynomial Ideals
• Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming
• Cayley-Bacharach theorems and conjectures
• Semidefinite Optimization and Convex Algebraic Geometry
• 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
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item

This page was built for publication: Sums of squares on the hypercube