On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
On the Integrality Gap of Degree-4 Sum of Squares for Planted Clique
复制标题
植集团4次平方和的完整性差距
DOI：
10.1145/3178538
复制
发表时间：
2016
期刊：
影响因子：
--
通讯作者：
T. Schramm
中科院分区：
文献类型：
--
作者：
Samuel B. Hopkins;Pravesh Kothari;Aaron Potechin;P. Raghavendra;T. Schramm
在随机图中找到大团的问题及其“种植”变体，即想要恢复添加到 Erdős-Rényi 图 G ∼ G(n,1/2) 中的大小为 ω > log (n) 的团，已经得到了深入研究。然而，现有的多项式时间算法只能恢复大小为 ω = Ω (√ n) 的植入团。相比之下，从理论上讲，只要 ω > log (n)，就可以恢复种植的派系。在这项工作中，我们继续研究平方和层次结构中的算法，以解决由 Meka、Potechin 和 Wigderson [2] 以及 Deshpande 和 Montanari [25] 开始的植集团问题。我们的主要结果是，除非 ω > √ n / polylog n，否则四级 SoS 不会恢复植入的团伙，从而改进了参考文献 [25] 中的界限 ω > n1/3。凯尔纳的一个论点表明，这个结果不能使用与先前作品相同的证书来证明。相反，我们的证明涉及构建和分析一个新的证书，通过“纠正”参考文献的证书来产生近乎严格的下界[2,25,27]。
The problem of finding large cliques in random graphs and its “planted” variant, where one wants to recover a clique of size ω > log (n) added to an Erdős-Rényi graph G ∼ G(n,1/2), have been intensely studied. Nevertheless, existing polynomial time algorithms can only recover planted cliques of size ω = Ω (√ n). By contrast, information theoretically, one can recover planted cliques so long as ω > log (n). In this work, we continue the investigation of algorithms from the Sum of Squares hierarchy for solving the planted clique problem begun by Meka, Potechin, and Wigderson [2] and Deshpande and Montanari [25]. Our main result is that degree four SoS does not recover the planted clique unless ω > √ n / polylog n, improving on the bound ω > n1/3 due to Reference [25]. An argument of Kelner shows that the this result cannot be proved using the same certificate as prior works. Rather, our proof involves constructing and analyzing a new certificate that yields the nearly tight lower bound by “correcting” the certificate of References [2, 25, 27].
影响因子：
2.5
作者：
Harrow, Aram W.;Montanaro, Ashley
通讯作者：
Montanaro, Ashley