The Spectrum of the Grigoriev–Laurent Pseudomoments

DOI10.1137/22M1511394MaRDI QIDQ6187076zbMATH OpenFDO

Authors Dmitriy Kunisky, Cristopher Moore

Publication date 10 January 2024

Published in SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

convex optimizationsemidefinite programmingrepresentation theorysum-of-squares

Mathematics Subject Classification ID

Eigenvalues, singular values, and eigenvectors (15A18) Semidefinite programming (90C22) Representations of finite symmetric groups (20C30)

Abstract: Grigoriev (2001) and Laurent (2003) independently showed that the sum-of-squares hierarchy of semidefinite programs does not exactly represent the hypercube ${pm1}^n$ until degree at least $n$ of the hierarchy. Laurent also observed that the pseudomoment matrices her proof constructs appear to have surprisingly simple and recursively structured spectra as $n$ increases. While several new proofs of the Grigoriev-Laurent lower bound have since appeared, Laurent's observations have remained unproved. We give yet another, representation-theoretic proof of the lower bound, which also yields exact formulae for the eigenvalues of the Grigoriev-Laurent pseudomoments. Using these, we prove and elaborate on Laurent's observations. Our arguments have two features that may be of independent interest. First, we show that the Grigoriev-Laurent pseudomoments are a special case of a Gram matrix construction of pseudomoments proposed by Bandeira and Kunisky (2020). Second, we find a new realization of the irreducible representations of the symmetric group corresponding to Young diagrams with two rows, as spaces of multivariate polynomials that are multiharmonic with respect to an equilateral simplex.

Recommendations

• Gram spectrahedra
• Sum of squares lower bounds from symmetry and a good story
• Sums of squares on the hypercube

Cites work

• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 51906 (Why is no real title available?)
• scientific article; zbMATH DE number 1489808 (Why is no real title available?)
• scientific article; zbMATH DE number 872231 (Why is no real title available?)
• scientific article; zbMATH DE number 911775 (Why is no real title available?)
• A nearly tight sum-of-squares lower bound for the planted clique problem
• A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
• An approach to obtaining global extremums in polynomial mathematical programming problems
• Complexity of Positivstellensatz proofs for the knapsack
• Exact Semidefinite Programming Relaxations with Truncated Moment Matrix for Binary Polynomial Optimization Problems
• Global optimization with polynomials and the problem of moments
• Homogeneous polynomial solutions to constant coefficient PDE's
• Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity
• Lower Bound for the Number of Iterations in Semidefinite Hierarchies for the Cut Polytope
• On the bit complexity of sum-of-squares proofs
• On the hardest problem formulations for the 0/1 Lasserre hierarchy
• SOS is not obviously automatizable, even approximately
• Semialgebraic Proofs and Efficient Algorithm Design
• Semidefinite Optimization and Convex Algebraic Geometry
• Semidefinite programming relaxations for semialgebraic problems
• Sparse sums of squares on finite abelian groups and improved semidefinite lifts
• Strongly regular graphs
• Sum of squares lower bounds for refuting any CSP
• Sum of squares lower bounds from symmetry and a good story
• Sum-of-squares Lower Bounds for Planted Clique
• Sum-of-squares hierarchies for binary polynomial optimization
• Sum-of-squares proofs and the quest toward optimal algorithms
• Sums of squares on the hypercube
• Sums of squares, moment matrices and optimization over polynomials

This page was built for publication: The Spectrum of the Grigoriev–Laurent Pseudomoments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6187076)