A NEARLY TIGHT SUM-OF-SQUARES LOWER BOUND FOR THE PLANTED CLIQUE PROBLEM

被引：75

作者：

Barak, Boaz ^{[1
]}

Hopkins, Samuel ^{[2
]}

Kelner, Jonathan ^{[3
]}

Kothari, Pravesh K. ^{[4
,5
]}

Moitra, Ankur ^{[3
]}

Potechin, Aaron ^{[5
]}

机构：

[1] Microsoft Res New England, Cambridge, MA 02142 USA

[2] Cornell Univ, Comp Sci, Ithaca, NY 14853 USA

[3] MIT, Sch Engn, 77 Massachusetts Ave, Cambridge, MA 02139 USA

[4] Princeton Univ, Princeton, NJ 08540 USA

[5] Inst Adv Study, Olden Lane, Princeton, NJ 08540 USA

来源：

SIAM JOURNAL ON COMPUTING | 2019年 / 48卷 / 02期

基金：

美国国家科学基金会;

关键词：

sum-of-squares; planted clique; lower bound; INFORMATION-THEORY; COMPLEXITY;

D O I：

10.1137/17M1138236

中图分类号：

TP301 [理论、方法];

学科分类号：

081202 ;

摘要：

We prove that with high probability over the choice of a random graph G from the Erdos-Renyi distribution G(n,1/2), the n(O)((d))-time degree d sum-of-squares (SOS) semidefinite programming relaxation for the clique problem will give a value of at least n(1/2-c(d/ log n)1/2 )or some constant c > 0. This yields a nearly tight n(1)(/2-o(1)) bound on the value of this program for any degree d = o(logn). 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.

引用

页码：687 / 735

页数：49