Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes

arXiv2009.01874MaRDI QIDQ6348362FDOQ6348362

Authors: Mrinalkanti Ghosh, Fernando Granha Jeronimo, Chris V. Jones, Aaron Potechin, Goutham Rajendran 

Publication date: 3 September 2020

Abstract: The Sum-of-Squares (SoS) hierarchy is a semi-definite programming meta-algorithm that captures state-of-the-art polynomial time guarantees for many optimization problems such as Max-$k$-CSPs and Tensor PCA. On the flip side, a SoS lower bound provides evidence of hardness, which is particularly relevant to average-case problems for which NP-hardness may not be available. In this paper, we consider the following average case problem, which we call the emph{Planted Affine Planes} (PAP) problem: Given $m$ random vectors $d_1,ldots,d_m$ in $mathbb{R}^n$, can we prove that there is no vector $vinmathbb{R}^n$ such that for all $uin[m]$, $langlev,d_{u}angl{e}^2=1$? In other words, can we prove that $m$ random vectors are not all contained in two parallel hyperplanes at equal distance from the origin? We prove that for $mleq{n}^{3/2-epsilon}$, with high probability, degree-$n^{Omega(epsilon)}$ SoS fails to refute the existence of such a vector $v$. When the vectors $d_1,ldots,d_m$ are chosen from the multivariate normal distribution, the PAP problem is equivalent to the problem of proving that a random $n$-dimensional subspace of $mathbb{R}^m$ does not contain a boolean vector. As shown by Mohanty--Raghavendra--Xu [STOC 2020], a lower bound for this problem implies a lower bound for the problem of certifying energy upper bounds on the Sherrington-Kirkpatrick Hamiltonian, and so our lower bound implies a degree-$n^{Omega(epsilon)}$ SoS lower bound for the certification version of the Sherrington-Kirkpatrick problem.

This page was built for publication: Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6348362)