@inproceedings{ee3762423dd04ca489e0bb6dc69d09a3,

title = "A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem",

abstract = "We prove that with high probability over the choice of a random graph G from the Erds-R{\'e}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.",

keywords = "Algorithm design and analysis, Computational complexity, Mathematical programming",

author = "Boaz Barak and Hopkins, {Samuel B.} and Jonathan Kelner and Pravesh Kothari and Ankur Moitra and Aaron Potechin",

year = "2016",

month = dec,

day = "14",

doi = "10.1109/FOCS.2016.53",

language = "English (US)",

series = "Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS",

publisher = "IEEE Computer Society",

pages = "428--437",

booktitle = "Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016",

address = "United States",

note = "57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016 ; Conference date: 09-10-2016 Through 11-10-2016",

}