A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem

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

Research output: Chapter in Book/Report/Conference proceedingConference contribution

36 Scopus citations

Abstract

We prove that with high probability over the choice of a random graph G from the Erds-Rényi distribution G(n,1/2), the no(d)-time degree d Sum-of-Squares 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 pseudo-calibration to construct Sum-of-Squares lower bounds. This framework is inspired by taking a computational analogue 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.

Original languageEnglish (US)
Title of host publicationProceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PublisherIEEE Computer Society
Pages428-437
Number of pages10
ISBN (Electronic)9781509039333
DOIs
StatePublished - Dec 14 2016
Event57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 - New Brunswick, United States
Duration: Oct 9 2016Oct 11 2016

Publication series

NameProceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
Volume2016-December
ISSN (Print)0272-5428

Other

Other57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
CountryUnited States
CityNew Brunswick
Period10/9/1610/11/16

All Science Journal Classification (ASJC) codes

  • Computer Science(all)

Keywords

  • Algorithm design and analysis
  • Computational complexity
  • Mathematical programming

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. B., Kelner, J., Kothari, P., Moitra, A., & Potechin, A. (2016). A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem. In Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 (pp. 428-437). [7782957] (Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS; Vol. 2016-December). IEEE Computer Society. https://doi.org/10.1109/FOCS.2016.53