TY - GEN
T1 - A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
AU - Barak, Boaz
AU - Hopkins, Samuel B.
AU - Kelner, Jonathan
AU - Kothari, Pravesh
AU - Moitra, Ankur
AU - Potechin, Aaron
N1 - Publisher Copyright:
© 2016 IEEE.
Copyright:
Copyright 2017 Elsevier B.V., All rights reserved.
PY - 2016/12/14
Y1 - 2016/12/14
N2 - 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.
AB - 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.
KW - Algorithm design and analysis
KW - Computational complexity
KW - Mathematical programming
UR - http://www.scopus.com/inward/record.url?scp=85009401001&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=85009401001&partnerID=8YFLogxK
U2 - 10.1109/FOCS.2016.53
DO - 10.1109/FOCS.2016.53
M3 - Conference contribution
AN - SCOPUS:85009401001
T3 - Proceedings - Annual IEEE Symposium on Foundations of Computer Science, FOCS
SP - 428
EP - 437
BT - Proceedings - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
PB - IEEE Computer Society
T2 - 57th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2016
Y2 - 9 October 2016 through 11 October 2016
ER -