SOS lower bound for exact planted clique
SOS lower bound for exact planted clique
复制标题
精确种植团的 SOS 下界
DOI：
--
复制
发表时间：
2021
期刊：
影响因子：
--
通讯作者：
Shuo Pang
中科院分区：
文献类型：
--
作者：
Shuo Pang
我们在 Erdös-Rényi 随机图 G(n, 1/2) 上证明了植集团问题的 SOS 度下界。对于团大小 ω = n1/2−ϵ，我们得到的界限是度 d = Ω(ϵ2 log n/ log log n)，这几乎是紧的。这改进了问题“软”版本的 [5] 的结果，其中由 x1 + ... + xn = ω 生成的等式公理族被放宽为一个不等式 x1 + ... + xn ≥ ω。作为技术副产品，我们还“自然化”了针对松弛问题开发和使用的某些技术。这包括一种定义伪期望的新方法，以及一种更鲁棒的方法来解决矩矩阵的粗对角化。
We prove a SOS degree lower bound for the planted clique problem on the Erdös-Rényi random graph G(n, 1/2). The bound we get is degree d = Ω(ϵ2 log n/ log log n) for clique size ω = n1/2−ϵ, which is almost tight. This improves the result of [5] for the "soft" version of the problem, where the family of the equality-axioms generated by x1 + ... + xn = ω is relaxed to one inequality x1 + ... + xn ≥ ω. As a technical by-product, we also "naturalize" certain techniques that were developed and used for the relaxed problem. This includes a new way to define the pseudo-expectation, and a more robust method to solve out the coarse diagonalization of the moment matrix.