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.

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 -