论文标题
算法接近半随机种植集团的阈值
Algorithms approaching the threshold for semi-random planted clique
论文作者
论文摘要
我们设计了新的多项式时间算法，用于在Feige和Kilian 2001介绍的半随机图模型中恢复种植的集团。如果该植物集团在图形中至少具有$ n^{2/3} $，则该模型的先前最佳算法是成功的。 2017）。我们的算法适用于接近$ n^{1/2} $的种植型尺寸 - 半随机模型中的信息理论阈值（Steinhardt 2017）和猜想的计算阈值，即使在更轻松的全范围模型中也是如此。该结果接近于Feige 2019和Steinhardt 2017的公开问题。 我们的算法基于较高的恒定程度总和的放松，并依靠一种新的概念连接，该概念连接转化了在不平衡的两部分ERDőS--rényi随机图中，将上限证书转换为半飞镖种植集团的算法。在我们的环境中，使用更高的水平总和是必不可少的：我们证明了基本SDP的下限，用于证明双石的基本限制，这表明基本的SDP无法成功，因为$ k = o（n^{2/3}）的植物丛无法成功。我们还提供了一些证据表明，我们当前算法的信息计算取舍可能是固有的，这可能是证明低度多项式模型中不平衡双智能的平均案例下限。
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian 2001. The previous best algorithms for this model succeed if the planted clique has size at least $n^{2/3}$ in a graph with $n$ vertices (Mehta, Mckenzie, Trevisan 2019 and Charikar, Steinhardt, Valiant 2017). Our algorithms work for planted-clique sizes approaching $n^{1/2}$ -- the information-theoretic threshold in the semi-random model (Steinhardt 2017) and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige 2019 and Steinhardt 2017. Our algorithms are based on higher constant degree sum-of-squares relaxation and rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers in unbalanced bipartite Erdős--Rényi random graphs into algorithms for semi-random planted clique. The use of a higher-constant degree sum-of-squares is essential in our setting: we prove a lower bound on the basic SDP for certifying bicliques that shows that the basic SDP cannot succeed for planted cliques of size $k =o(n^{2/3})$. We also provide some evidence that the information-computation trade-off of our current algorithms may be inherent by proving an average-case lower bound for unbalanced bicliques in the low-degree-polynomials model.
