Back to Search
Start Over
A tight degree 4 sum-of-squares lower bound for the Sherrington–Kirkpatrick Hamiltonian
- Source :
- Mathematical Programming. 190:721-759
- Publication Year :
- 2020
- Publisher :
- Springer Science and Business Media LLC, 2020.
-
Abstract
- We show that, if $\mathbf{W} \in \mathbb{R}^{N \times N}_{\mathsf{sym}}$ is 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} \cdot \mathbf{x}^\top \mathbf{W} \mathbf{x}$ under the constraints $x_i^2 - 1 = 0$ (i.e. $\mathbf{x} \in \{ \pm 1 \}^N$) that is asymptotically smaller than $\lambda_{\max}(\mathbf{W}) \approx 2$. We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as $N \to \infty$, by proposing an approximate pseudomoment construction.<br />Comment: 34 pages. Minor text revisions; closest to published version to appear in Mathematical Programming
- Subjects :
- FOS: Computer and information sciences
General Mathematics
Gaussian
0211 other engineering and technologies
FOS: Physical sciences
010103 numerical & computational mathematics
02 engineering and technology
Lambda
01 natural sciences
Upper and lower bounds
Combinatorics
symbols.namesake
Computer Science - Data Structures and Algorithms
FOS: Mathematics
Data Structures and Algorithms (cs.DS)
0101 mathematics
Mathematics - Optimization and Control
Condensed Matter - Statistical Mechanics
Mathematics
High probability
021103 operations research
Conjecture
Statistical Mechanics (cond-mat.stat-mech)
Probability (math.PR)
Explained sum of squares
Optimization and Control (math.OC)
symbols
Hamiltonian (quantum mechanics)
Mathematics - Probability
Software
Subjects
Details
- ISSN :
- 14364646 and 00255610
- Volume :
- 190
- Database :
- OpenAIRE
- Journal :
- Mathematical Programming
- Accession number :
- edsair.doi.dedup.....6b2030618e6ae38fbdccdc180c45dab9