@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",
}