Abstract
Planted clique is a basic problem in average-case analysis that has found numerous applications, including in discovering motifs in biological networks, computing the best Nash equilibrium, property testing, sparse PCA, compressed sensing, cryptography and mathematical finance. In this work, we prove a nearly optimal lower bound against the Sum-of-Squares hierarchy for it. Previously, it was possible that the Sum-of-Squares hierarchy might be able to find planted cliques of size $n^{\epsilon}$ for any $\epsilon > 0$ in polynomial time. We prove that the degree d program has an integrality gap of at least $n^{1/2 - c \sqrt{d / log n}}$ for some constant $c > 0$.
Moreover our approach is based on a new framework that we call pseudo-calibration, which yields a general recipe for constructing good pseudo-distributions (i.e., dual certificates for the Sum-of-Squares semidefinite program). This framework also sheds further light on the ways in which the Sum-of-Squares hierarchy is qualitatively stronger than others, and what is needed to fool it.
Joint work with Boaz Barak, Sam Hopkins, Jon Kelner, Pravesh Kothari and Aaron Potechin