Sum-of-squares Lower Bounds for Planted Clique

DOI10.1145/2746539.2746600zbMATH Open1321.05241arXiv1503.06447OpenAlexW2033515640WikidataQ56210431 ScholiaQ56210431MaRDI QIDQ2941492FDOQ2941492

Authors: Raghu Meka, Aaron Potechin, A. Wigderson 

Publication date: 21 August 2015

Published in: Proceedings of the forty-seventh annual ACM symposium on Theory of Computing (Search for Journal in Brave)

Abstract: 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 ~ sqrt(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^{1/2r} (up to logarithmic factors). Thus, for any constant number of rounds planted cliques of size n^{o(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.

Full work available at URL: https://arxiv.org/abs/1503.06447

Recommendations

• A nearly tight sum-of-squares lower bound for the planted clique problem
• SOS lower bound for exact planted clique
• On the integrality gap of degree-4 sum of squares for planted clique
• On the integrality gap of degree-4 sum of squares for planted clique
• The Ehrenfeucht-Fraïssé method and the planted clique conjecture
• A simpler characterization of a spectral lower bound on the clique number
• Algorithmic lower bounds for problems parameterized by clique-width
• A new approach to the planted clique problem
• Almost Optimal Lower Bounds for Problems Parameterized by Clique-Width
• Statistical algorithms and a lower bound for detecting planted cliques

Mathematics Subject Classification ID

Random graphs (graph-theoretic aspects) (05C80) Random matrices (algebraic aspects) (15B52) Analysis of algorithms and problem complexity (68Q25) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Shortest-path queries in static networks
• Approximate distance oracles
• On sparse spanners of weighted graphs
• Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
• On approximate distance labels and routing schemes with affine stretch
• Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
• Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
• Near-Linear Time Construction of Sparse Neighborhood Covers
• Approximate distance oracles with constant query time
• Fast C-K-R partitions of sparse graphs
• Automata, Languages and Programming
• Ramsey partitions and proximity data structures

Cited In (32)

• Notes on computational hardness of hypothesis testing: predictions using the low-degree likelihood ratio
• Perfect matching in random graphs is as hard as Tseitin
• Generalized rank-breaking: computational and statistical tradeoffs
• Subexponential-time algorithms for sparse PCA
• Sherali-Adams integrality gaps matching the log-density threshold
• The Lovász theta function for random regular graphs and community detection in the hard regime
• On the integrality gap of degree-4 sum of squares for planted clique
• Tensor clustering with planted structures: statistical optimality and computational limits
• Cryptography from planted graphs: security with logarithmic-size messages
• Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
• A new approach to the planted clique problem
• Bounds on the norms of uniform low degree graph matrices
• The Lovász theta function for random regular graphs and community detection in the hard regime
• Statistical algorithms and a lower bound for detecting planted cliques
• Sum of squares lower bounds from symmetry and a good story
• Sum-of-squares bounds via Boolean function analysis
• Proof complexity and beyond. Abstracts from the workshop held March 24--29, 2024
• How to hide a clique?
• Bilu-Linial stability, certified algorithms and the independent set problem
• The Spectrum of the Grigoriev–Laurent Pseudomoments
• A Nearly Tight Sum-of-Squares Lower Bound for the Planted Clique Problem
• Title not available (Why is that?)
• Sum of Squares Bounds for the Empty Integral Hull Problem
• Random Tensors and Planted Cliques
• A Lasserre lower bound for the min-sum single machine scheduling problem
• On the integrality gap of degree-4 sum of squares for planted clique
• An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
• Hidden Hamiltonian cycle recovery via linear programming
• The overlap gap property in principal submatrix recovery
• Sum-of-squares lower bounds for densest \(k\)-subgraph
• Statistical algorithms and a lower bound for detecting planted cliques
• Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials

Uses Software

• Graphs

This page was built for publication: Sum-of-squares Lower Bounds for Planted Clique

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2941492)