Sum-of-squares Lower Bounds for Planted Clique
Sum-of-squares Lower Bounds for Planted Clique
复制标题
种植集团的平方和下界
DOI：
--
复制
发表时间：
2015
期刊：
影响因子：
--
通讯作者：
A. Wigderson
中科院分区：
文献类型：
--
作者：
Raghu Meka;Aaron Potechin;A. Wigderson
在随机图中找到了随机图和密切相关的“种植”集团的群集，其中大小K在随机的G（n，1/2）图中种植，尽管大量努力，最知名的多项式算法仅解决了k =θ（√n）的问题。降低该模型的绑定：对于G（N，1/2）中的所有图，SOS层次结构的R圆形无法找到种植的K-clique，除非K-≥（√n/log n）1/rcr该强大的算法的恒定数量的大小号（1）无法找到。从程度的下限Pitivestellensatz证明系统。对于每个固定的输入图。一个是关联方案的理论，尤其是约翰逊方案的特征空间和特征值方法将在其他地方有用。
Finding cliques in random graphs and the closely related "planted" clique variant, where a clique of size k is planted in a random G(n,1/2) graph, have been the focus of substantial study in algorithm design. Despite much effort, the best known polynomial-time algorithms only solve the problem for k = Θ(√n). In this paper we study the complexity of the planted clique problem under algorithms from the Sum-Of-Squares hierarchy. We prove the first average case lower bound for this model: for almost all graphs in G(n,1/2), r rounds of the SOS hierarchy cannot find a planted k-clique unless k ≥ (√n/log n)1/rCr. Thus, for any constant number of rounds planted cliques of size no(1) cannot be found by this powerful class of algorithms. This is shown via an integrability gap for the natural formulation of maximum clique problem on random graphs for SOS and Lasserre hierarchies, which in turn follow from degree lower bounds for the Positivestellensatz proof system. We follow the usual recipe for such proofs. First, we introduce a natural "dual certificate" (also known as a "vector-solution" or "pseudo-expectation") for the given system of polynomial equations representing the problem for every fixed input graph. Then we show that the matrix associated with this dual certificate is PSD (positive semi-definite) with high probability over the choice of the input graph.This requires the use of certain tools. One is the theory of association schemes, and in particular the eigenspaces and eigenvalues of the Johnson scheme. Another is a combinatorial method we develop to compute (via traces) norm bounds for certain random matrices whose entries are highly dependent; we hope this method will be useful elsewhere.