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-kk-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 mm random vectors d1,…,dmd_1,\ldots,d_m in Rn\mathbb{R}^n, can we prove that there is no vector v∈Rnv \in \mathbb{R}^n such that for all u∈[m]u \in [m], ⟨v,du⟩2=1\langle v, d_u\rangle^2 = 1? In other words, can we prove that mm random vectors are not all contained in two parallel hyperplanes at equal distance from the origin? We prove that for m≤n3/2−εm \leq n^{3/2-ε}, with high probability, degree-nΩ(ε)n^{Ω(ε)} SoS fails to refute the existence of such a vector vv. When the vectors d1,…,dmd_1,\ldots,d_m are chosen from the multivariate normal distribution, the PAP problem is equivalent to the problem of proving that a random nn-dimensional subspace of Rm\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Ω(ε)n^{Ω(ε)} SoS lower bound for the certification version of the Sherrington-Kirkpatrick problem.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.