A nearly tight sum-of-squares lower bound for the planted clique problem

Boaz Barak, Samuel Hopkins, Jonathan Kelner, Pravesh K. Kothari, Ankur Moitra, Aaron Potechin

Research output: Contribution to journalArticle

2 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)687-735
Number of pages49
JournalSIAM Journal on Computing
Volume48
Issue number2
DOIs
StatePublished - Jan 1 2019

All Science Journal Classification (ASJC) codes

  • Computer Science(all)
  • Mathematics(all)

Keywords

  • Lower bound
  • Planted clique
  • Sum-of-squares

Fingerprint Dive into the research topics of 'A nearly tight sum-of-squares lower bound for the planted clique problem'. Together they form a unique fingerprint.

  • Cite this

    Barak, B., Hopkins, S., Kelner, J., Kothari, P. K., Moitra, A., & Potechin, A. (2019). A nearly tight sum-of-squares lower bound for the planted clique problem. SIAM Journal on Computing, 48(2), 687-735. https://doi.org/10.1137/17M1138236