论文标题
Sherrington-Kirkpatrick通过种植的仿射平面
Sum-of-Squares Lower Bounds for Sherrington-Kirkpatrick via Planted Affine Planes
论文作者
论文摘要
平方级（SOS）层次结构是一个半明确编程元算法，可捕获许多优化问题（例如最大$ K $ -CSPS和TENSOR PCA）的最先进的多项式时间保证。另一方面，SOS下限提供了硬度的证据，这与可能无法提供NP固定度的平均案例问题特别相关。 在本文中，我们考虑以下平均情况问题，我们将其称为\ emph {种植的仿射平面}（pap）问题：给定$ m $随机矢量$ d_1，\ ldots，\ ldots，d_m $ in $ \ mathbb {r}^n $，我们可以证明没有vector $ v \ in \ in $ v \ n $ n $ n $ n $ y] $ \ langle v，d_u \ rangle^2 = 1 $？换句话说，我们能否证明$ m $随机向量并非全部包含在两个平行的超重样本中，距离原始距离相等距离？我们证明，对于$ m \ leq n^{3/2-ε} $，具有很高的概率，学位 - $ n^{ω（ε）} $ sos $ sos无法反驳这种向量$ v $的存在。 当向量$ d_1，\ ldots，d_m $从多元正态分布中选择D_M $时，PAP问题等同于证明$ \ Mathbb {r}^m $的随机$ n $二维子空间不包含布尔值。如Mohanty-Raghavendra-Xu [STOC 2020]所示，对于此问题的下限，暗示着在Sherrington-kirkpatrick Hamiltonian上证明能量上限的问题，因此我们的下限暗示了$ n^{ω（ω（ε）} $ sos sos wisterifficity-shimefifical shyserififice shyserife n shy shy shy shyring sherring sherring sherring sherring sherring sherring sherring sherring sherring sherring sherring sherring sherring。
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 $v \in \mathbb{R}^n$ such that for all $u \in [m]$, $\langle v, d_u\rangle^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 $m \leq n^{3/2-ε}$, with high probability, degree-$n^{Ω(ε)}$ 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^{Ω(ε)}$ SoS lower bound for the certification version of the Sherrington-Kirkpatrick problem.
