Sum-of-Squares Lower Bounds for Densest k-Subgraph
Sum-of-Squares Lower Bounds for Densest k-Subgraph
复制标题
最稠 k 子图的平方和下界
DOI：
10.1145/3564246.3585221
复制
发表时间：
2023
期刊：
影响因子：
--
通讯作者：
Xu, Jeff
中科院分区：
文献类型：
--
作者：
Jones, Chris;Potechin, Aaron;Rajendran, Goutham;Xu, Jeff
给定一个图和一个整数，Densestk-子图是在k个顶点上寻找边数最多的子图的算法。这是一个基本问题，几十年来一直受到深入研究，应用范围广泛。由于Bhaskara等人[STOC '10]，最先进的算法是O（n1/4 +）因子近似（对于任何> 0）。此外，所谓的对数密度框架预测这是最优的，也就是说，一个有效的算法不可能达到O（n1/4 −）-因子近似。在一般情况下，Densestk-Subgraph是一个典型的噪声推理任务，它被证明具有计算-计算间隙。在这项工作中，我们通过显示与强大的平方和（SoS）算法相匹配的下界，为Densestk-Subgraph提供了最强有力的证据。SoS算法是一种基于凸规划的元算法，可以为许多优化和推理问题提供最先进的算法保证。Fork≤n1/2，我们得到了一个degreenδSoS下界的硬制度的预测的对数密度框架。为了证明这一点，我们利用现代框架证明SoS下界的平均情况下的问题由Barak等人开创。[FOCS '16]。一个关键的问题是，输入中的小的密度高于平均值的子图将极大地影响子图周围的候选伪期望算子的值。为了应对这一挑战，我们设计了一个新的矩阵分解方案的基础上积极的最小顶点分离器。然后，我们证明了一个交叉权衡引理，表明使用此分离器时的误差项确实很小。
Given a graph and an integerk, Densestk-Subgraph is the algorithmic task of finding the subgraph onkvertices with the maximum number of edges. This is a fundamental problem that has been subject to intense study for decades, with applications spanning a wide variety of fields. The state-of-the-art algorithm is anO(n1/4 +)-factor approximation (for any > 0) due to Bhaskara et al. [STOC ’10]. Moreover, the so-calledlog-density frameworkpredicts that this is optimal, i.e. it is impossible for an efficient algorithm to achieve anO(n1/4 −)-factor approximation. In the average case, Densestk-Subgraph is a prototypical noisy inference task which is conjectured to exhibit astatistical-computational gap.In this work, we provide the strongest evidence yet of hardness for Densestk-Subgraph by showing matching lower bounds against the powerful Sum-of-Squares (SoS) algorithm, a meta-algorithm based on convex programming that achieves state-of-art algorithmic guarantees for many optimization and inference problems. Fork≤n1/2, we obtain a degreenδSoS lower bound for the hard regime as predicted by the log-density framework.To show this, we utilize the modern framework for proving SoS lower bounds on average-case problems pioneered by Barak et al. [FOCS ’16]. A key issue is that small denser-than-average subgraphs in the input will greatly affect the value of the candidate pseudoexpectation operator around the subgraph. To handle this challenge, we devise a novel matrix factorization scheme based on thepositive minimum vertex separator. We then prove an intersection tradeoff lemma to show that the error terms when using this separator are indeed small.
登录
查看更多内容
DOI：
10.1145/3055399.3055438
发表时间：
2016-10
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Pravesh Kothari;Raghu Meka;P. Raghavendra
通讯作者：
Pravesh Kothari;Raghu Meka;P. Raghavendra
通过平方和进行异常值稳健矩估计
DOI：
--
发表时间：
2017
期刊：
arXiv.org
影响因子：
--
作者：
Pravesh Kothari;David Steurer
通讯作者：
David Steurer
DOI：
--
发表时间：
2020-05
期刊：
--
影响因子：
--
作者：
Matthew Brennan;Guy Bresler
通讯作者：
Matthew Brennan;Guy Bresler
DOI：
10.1145/3055399.3055412
发表时间：
2016-11
期刊：
Proceedings of the 49th Annual ACM SIGACT Symposium on Theory of Computing
影响因子：
--
作者：
Pasin Manurangsi
通讯作者：
Pasin Manurangsi
影响因子：
1.9
作者：
Ames, Brendan P. W.
通讯作者：
Ames, Brendan P. W.