Sum-of-squares Lower Bounds for Planted Clique
From MaRDI portal
Publication:2941492
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)
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.
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
Cites work
- Approximate distance oracles
- Approximate distance oracles with constant query time
- Automata, Languages and Programming
- Distance Oracles for Unweighted Graphs: Breaking the Quadratic Barrier with Constant Additive Error
- Fast Algorithms for Constructing t-Spanners and Paths with Stretch t
- Fast C-K-R partitions of sparse graphs
- Near-Linear Time Construction of Sparse Neighborhood Covers
- On approximate distance labels and routing schemes with affine stretch
- On sparse spanners of weighted graphs
- Ramsey partitions and proximity data structures
- Scale-oblivious metric fragmentation and the nonlinear Dvoretzky theorem
- Shortest-path queries in static networks
Cited in
(32)- Optimization over the Boolean hypercube via sums of nonnegative circuit polynomials
- Statistical algorithms and a lower bound for detecting planted cliques
- A nearly tight sum-of-squares lower bound for the planted clique problem
- 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
- Recovering a hidden community beyond the Kesten-Stigum threshold in \(O(| E|\log^\ast| V|)\) time
- Cryptography from planted graphs: security with logarithmic-size messages
- A new approach to the planted clique problem
- Bounds on the norms of uniform low degree graph matrices
- Statistical algorithms and a lower bound for detecting planted cliques
- The Lovász theta function for random regular graphs and community detection in the hard regime
- 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
- scientific article; zbMATH DE number 7378399 (Why is no real title available?)
- Sum of Squares Bounds for the Empty Integral Hull Problem
- Random Tensors and Planted Cliques
- An unbounded sum-of-squares hierarchy integrality gap for a polynomially solvable problem
- 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
- Hidden Hamiltonian cycle recovery via linear programming
- The overlap gap property in principal submatrix recovery
- Sum-of-squares lower bounds for densest \(k\)-subgraph
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)
