A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak Harvard University Harvard John A. Paulson School of Engineering and Applied Sciences, Part of the work was done while the author was at Microsoft Research New England. Samuel B. Hopkins Cornell University Partially supported by an NSF GRFP under grant no. 1144153. Part of this work was done while the author was at Microsoft Research New England. Jonathan Kelner MIT Partially supported by NSF Award 1111109. Pravesh K. Kothari UT Austin Part of the work was done while the author was at Microsoft Research New England. Ankur Moitra MIT Partially supported by NSF CAREER Award CCF-1453261, a grant from the MIT NEC Corporation and a Google Faculty Research Award. Aaron Potechin Cornell University Part of the work was done while the author was at Microsoft Research New England.
Abstract
We prove that with high probability over the choice of a random graph $G$ from the Erdős–Rényi distribution $G(n,1/2)$ , the $n^{O(d)}$ -time degree $d$ Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least $n^{1/2-c(d/\log n)^{1/2}}$ for some constant $c>0$ . This yields a nearly tight $n^{1/2-o(1)}$ bound on the value of this program for any degree $d=o(\log n)$ . Moreover we introduce a new framework that we call pseudo-calibration to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog of Bayesian probability theory. It yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program), and sheds further light on the ways in which this hierarchy differs from others.
中文速览
在随机图中找隐藏团（planted clique）是平均情形复杂性的核心难题，理论上最好的多项式时间算法只能找到大小约为√n 的团，但一直不清楚更强的凸优化工具——平方和（Sum-of-Squares，SoS）层次结构——能否突破这一瓶颈。本文证明：对于任意次数 d = o(log n) 的 SoS 松弛，其整数间隙至少为 n^{1/2 − o(1)}，即该程序在随机图上给出的目标值接近 √n，却无法区分是否真的存在大团，从而几乎紧地确认了 SoS 无法在多项式时间内找到比 √n 小得多的团。为了构造这一下界，作者提出了名为"伪校准"（pseudo-calibration）的新框架：将贝叶斯概率论的计算类比引入 SoS 分析，用"计算受限的贝叶斯观察者对条件期望的最佳近似"来系统地构造满足 SoS 约束的伪分布（pseudo-distribution），不仅统一并大幅推广了前人的结果，还为理解 SoS 比其他层次结构更强的原因提供了新视角，对未来设计 SoS 算法同样有潜在指导价值。
原文 arXiv:1604.03084;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1604.03084v2