@article{0a3fbf5486a34457bbbb43f4392d21b9,
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 Erd\H os-R{\'e}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.",
keywords = "Lower bound, Planted clique, Sum-of-squares",
author = "Boaz Barak and Samuel Hopkins and Jonathan Kelner and Kothari, {Pravesh K.} and Ankur Moitra and Aaron Potechin",
note = "Funding Information: \ast Received by the editors July 10, 2017; accepted for publication (in revised form) January 22, 2019; published electronically April 30, 2019. An extended abstract of this work appeared in Proceedings of the 57th Annual IEEE Symposium on Foundations of Computer Science, 2016. http://www.siam.org/journals/sicomp/48-2/M113823.html Funding: The second author's research was partially supported by NSF GRFP grant 1144153 and by NSF grants 1408673 and 1350196. The third author's research was partially supported by NSF award 1111109. The fifth author's research was partially supported by NSF CAREER award CCF-1453261, a grant from the MIT NEC Corporation, and a Google Faculty Research Award. \dagger Microsoft Research New England, Cambridge, MA 02142 (b@boazbarak.org). \ddagger Computer Science, Cornell University, Ithaca, NY 14853 (samhop@cs.cornell.edu). \S MIT, School of Engineering, Cambridge, MA 02139 (kelner@mit.edu, moitra@mit.edu). \P Princeton University and Institute for Advanced Study, Princeton, NJ 08540 (kotpravesh@gmail. com). \| Institute for Advanced Study, Princeton, NJ 08540 (apotechin@ias.edu). Funding Information: The second author's research was partially supported by NSF GRFP grant 1144153 and by NSF grants 1408673 and 1350196. The third author's research was partially supported by NSF award 1111109. The fifth author's research was partially supported by NSF CAREER award CCF-1453261, a grant from the MIT NEC Corporation, and a Google Faculty Research Award. Publisher Copyright: {\textcopyright} 2019 Society for Industrial and Applied Mathematics",
year = "2019",
doi = "10.1137/17M1138236",
language = "English (US)",
volume = "48",
pages = "687--735",
journal = "SIAM Journal on Computing",
issn = "0097-5397",
publisher = "Society for Industrial and Applied Mathematics Publications",
number = "2",
}