A tight degree 4 sum-of-squares lower bound for the Sherrington-Kirkpatrick Hamiltonian

• 成果类型: Article
• 署名作者: Kunisky, Dmitriy; Bandeira, Afonso S.
• 署名单位: New York University; Swiss Federal Institutes of Technology Domain; ETH Zurich
• 刊物名称: MATHEMATICAL PROGRAMMING
• ISSN/ISSBN: 0025-5610
• DOI: 10.1007/s10107-020-01558-2
• 发表日期: 2021
• 页码: 721-759
• 关键词: Approximation; optimization; hierarchies; number; MODEL

摘要

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.