期刊名称：Electronic Colloquium on Computational Complexity
印刷版ISSN：1433-8092
出版年度：2016
卷号：2016
出版社：Universität Trier, Lehrstuhl für Theoretische Computer-Forschung
摘要：We prove that with high probability over the choice of a random graph G from the Erd\H{o}s-R\'enyi distribution G ( n 1 2) , the n O ( d ) -time degree d Sum-of-Squares semidefinite programming relaxation for the clique problem will give a value of at least n 1 2 − c ( d log n ) 1 2 for some constant 0"> c 0 . This yields a nearly tight n 1 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 \emph{pseudo-calibration} to construct Sum of Squares lower bounds. This framework is inspired by taking a computational analog 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.
关键词：lower bounds ; planted clique ; random matrices ; Semidefinite programming ; Sum of Squares
