We prove that with high probability over the choice of a random graph G from the Erd\H os-Rényi distribution G(n, 1/2), the nO(d)-time degree d sum-of-squares (SOS) semidefinite programming relaxation for the clique problem will give a value of at least n1/2 - c(d/ log n)1/2 for some constant c > 0. This yields a nearly tight n1/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 pseudocalibration to construct SOS lower bounds. This framework is inspired by taking a computational analogue of Bayesian probability theory. It yields a general recipe for constructing good pseudodistributions (i.e., dual certificates for the SOS semidefinite program) and sheds further light on the ways in which this hierarchy differs from others.
All Science Journal Classification (ASJC) codes
- Computer Science(all)
- Lower bound
- Planted clique