The Spectrum of the Grigoriev–Laurent Pseudomoments

DOI10.1137/22M1511394zbMATH Open1529.90056arXiv2203.05693MaRDI QIDQ6187076FDOQ6187076

Authors: Dmitriy Kunisky, Cristopher Moore 

Publication date: 10 January 2024

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

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.

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

Recommendations

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

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)

Cites Work

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

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)