A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
Boaz Barak Thanks: 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. Affiliation: Harvard University Samuel B. Hopkins Thanks: 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. Affiliation: Cornell University Jonathan Kelner Thanks: Partially supported by NSF Award 1111109. Affiliation: MIT Pravesh K. Kothari Thanks: Part of the work was done while the author was at Microsoft Research New England. Affiliation: UT Austin Ankur Moitra Thanks: Partially supported by NSF CAREER Award CCF-1453261, a grant from the MIT NEC Corporation and a Google Faculty Research Award. Affiliation: MIT Aaron Potechin Thanks: Part of the work was done while the author was at Microsoft Research New England. Affiliation: Cornell University
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.
原文 arXiv:1604.03084;中英对照 + 大白话阅读 https://aha.fim.ai/paper/1604.03084v2