2019/07/31 by Dmitriy Kunisky, Afonso S. Bandeira
Computer Science · Mathematics · Physics and Astronomy · #Advanced Optimization Algorithms Research #Complexity and Algorithms in Graphs #Conjecture #Constant (computer programming) #Degree (music) #Gaussian #Hamiltonian (control theory) #Relaxation (psychology) #Tensor decomposition and applications #Upper and lower bounds #cond-mat.stat-mech #cs.DS #math.OC #math.PR
paper · pdf · doi:10.1007/s10107-020-01558-2
34 pages. Minor text revisions; closest to published version to appear in Mathematical Programming
openalex created_date 2019/08/13 · openalex publication_date 2020/11/05 · arxiv created 2020/11/07 · arxiv updated 2020/11/10 · openalex updated_date 2026/08/06
We show that, if \varvecW is an N × N 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 ⋅ \varvecx^\top \varvecW \varvecx under the constraints xi2 - 1 = 0 (i.e. \varvecx∈ \± 1 \N ) that is asymptotically smaller than λ max (\varvecW) ≈ 2 . We also conjecture a proof technique for lower bounds against sum-of-squares relaxations of any degree held constant as N → ∞ , by proposing an approximate pseudomoment construction.