Algorithms Approaching the Threshold for Semi-random Planted Clique
Algorithms Approaching the Threshold for Semi-random Planted Clique
复制标题
接近半随机植入派系阈值的算法
DOI：
10.1145/3564246.3585184
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Steurer, David
中科院分区：
文献类型：
--
作者：
Buhai, Rares-Darius;Kothari, Pravesh K.;Steurer, David
在Feige和Kilian提出的半随机图模型中，我们设计了新的多项式时间算法来恢复种植集团。如果在n个顶点的图中，种植团的大小至少为n 2/3，则该模型的以前最好的算法是成功的。我们的算法工作的种植集团的大小接近n1/2-信息理论的阈值在半随机模型和一个简化的计算阈值，即使在更容易的全随机模型。为了生成半随机种植团模型中的图，我们首先以1/2的边概率种植一个大小为k的顶点图团，然后逆向添加或删除不与种植团接触的任意数目的边，并删除超出种植团的任何边子集。对于每个k>0，我们给出了一个O（1/k）时间算法，当k ≥ n（1/2+ k）时，该算法恢复了该模型中的一个团的大小.事实上，我们的算法以很高的概率计算出一个包含种植集团的大小为k的约n/k个集团的列表。我们的算法还扩展到任意边概率p，并在p ≤ 1−n− 0.001时改进了以前的最佳保证。我们的算法依赖于一个新的概念连接，将不平衡二部随机图中二边数上界的证明转化为半随机种植团的算法。类似于完全随机模型的最优算法，以前的半随机种植集团的最佳保证对应于基于邻接矩阵特征值的biclique数的谱松弛。我们构造了一个SDP下界，表明以前的工作中的then 2/3阈值是这些谱弛豫的固有限制。我们超越了这一限制，使用高阶平方和松弛biclique numbers.我们还提供了一些证据，我们目前的算法的信息计算权衡可能是固有的，通过证明一个平均情况下的下界不平衡bicliques在低次多项式模型。
We design new polynomial-time algorithms for recovering planted cliques in the semi-random graph model introduced by Feige and Kilian. The previous best algorithms for this model succeed if the planted clique has size at leastn2/3in a graph withnvertices. Our algorithms work for planted-clique sizes approachingn1/2— the information-theoretic threshold in the semi-random model and a conjectured computational threshold even in the easier fully-random model. This result comes close to resolving open questions by Feige and Steinhardt.To generate a graph in the semi-random planted-clique model, we first 1) plant a clique of sizekin ann-vertex –graph with edge probability 1/2 and then adversarially add or delete an arbitrary number edges not touching the planted clique and delete any subset of edges going out of the planted clique. For every є>0, we give annO(1/є)-time algorithm that recovers a clique of sizekin this model wheneverk≥n1/2+є. In fact, our algorithm computes, with high probability, a list of aboutn/kcliques of sizekthat contains the planted clique. Our algorithms also extend to arbitrary edge probabilitiespand improve on the previous best guarantee wheneverp≤ 1−n−0.001.Our algorithms rely on a new conceptual connection that translates certificates of upper bounds on biclique numbers inunbalancedbipartite –random graphs into algorithms for semi-random planted clique. Analogous to the (conjecturally) optimal algorithms for the fully-random model, the previous best guarantees for semi-random planted clique correspond to spectral relaxations of biclique numbers based on eigenvalues of adjacency matrices. We construct an SDP lower bound that shows that then2/3threshold in prior works is an inherent limitation of these spectral relaxations. We go beyond this limitation by using higher-order sum-of-squares relaxations for biclique numbers.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 polynomial model.
登录
查看更多内容
列表可解码线性回归
DOI：
--
发表时间：
2019
期刊：
Advances in neural information processing systems
影响因子：
--
作者：
Karmalkar, Sushrut;Klivans, Adam;Kothari, Pravesh
通讯作者：
Kothari, Pravesh
通过全局相关性舍入半定编程层次结构
DOI：
10.1109/focs.2011.95
发表时间：
2011
期刊：
2011 IEEE 52nd Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
B. Barak;P. Raghavendra;David Steurer
通讯作者：
David Steurer
非球形混合物的异常值稳健聚类
DOI：
--
发表时间：
2020
期刊：
arXiv.org
影响因子：
--
作者：
Ainesh Bakshi;Pravesh Kothari
通讯作者：
Pravesh Kothari
半随机图问题的启发式方法
DOI：
--
发表时间：
2001
期刊：
Journal of computer and system sciences (Print)
影响因子：
--
作者：
U. Feige;J. Kilian
通讯作者：
J. Kilian
用于稳健社区检测的极小极大率
DOI：
--
发表时间：
2022
期刊：
IEEE Annual Symposium on Foundations of Computer Science
影响因子：
--
作者：
Allen Liu;Ankur Moitra
通讯作者：
Ankur Moitra