A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian
Metadata only
Date
2020-11Type
- Journal Article
Abstract
We show that, if W is an N xN matrix drawn from the gaussian orthogonal ensemble, then with high probability the degree 4 sum-of-squares relaxation cannot certify an upper bound on the objective N-1 center dot x(perpendicular to) Wx under the constraints x(i)(2) - 1 = 0 (i.e. x is an element of {+/- 1}(N)) that is asymptotically smaller than lambda(max)(W) approximate to 2. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as N -> infinity, by proposing an approximate pseudomoment construction. Show more
Publication status
publishedExternal links
Journal / series
Mathematical ProgrammingVolume
Pages / Article No.
Publisher
SpringerSubject
Sum-of-squares; Convex optimization; Average-case computational complexity; Semidefinite programming; Spin glassOrganisational unit
09679 - Bandeira, Afonso / Bandeira, Afonso
Related publications and datasets
Is new version of: http://hdl.handle.net/20.500.11850/392254
More
Show all metadata