Talks
Spring 2016

# Planted Clique, Sum-of-Squares and Pseudo-Calibration

Wednesday, May 4, 2016 9:30 am10:15 am PDT

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$.