# Improved Sum-of-Squares Lower Bounds for Hidden Clique and Hidden Submatrix Problems

arXiv: https://arxiv.org/abs/1502.06590 · HTML: https://mlsanity.com/paper/1502.06590/

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 23 Feb 2015.

## Built on by (most cited first, 9 of 9)

- [Robust Estimation for Random Graphs](https://mlsanity.com/paper/2111.05320/) (2021)
- [Informative core identification in complex networks](https://mlsanity.com/paper/2101.06388/) (2021)
- [Inferring Hidden Structures in Random Graphs](https://mlsanity.com/paper/2110.01901/) (2021)
- [Planted Bipartite Graph Detection](https://mlsanity.com/paper/2302.03658/) (2023)
- [Logspace Reducibility From Secret Leakage Planted Clique](https://mlsanity.com/paper/2107.11886/) (2021)
- [Distribution free optimality intervals for clustering](https://mlsanity.com/paper/2107.14442/) (2021)
- [Concentration of polynomial random matrices via Efron-Stein inequalities](https://mlsanity.com/paper/2209.02655/) (2022)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)
- [Computational Lower Bounds for Regret Minimization in Normal-Form Games](https://mlsanity.com/paper/2411.01721/) (2024)

## Abstract (arXiv)

Given a large data matrix A∈ℝn× n, we consider the problem of determining whether its entries are i.i.d. with some known marginal distribution Aij~ P0, or instead A contains a principal submatrix A_sf Q,sf Q whose entries have marginal distribution Aij~ P1neq P0. As a special case, the hidden (or planted) clique problem requires to find a planted clique in an otherwise uniformly random graph. Assuming unbounded computational resources, this hypothesis testing problem is statistically solvable provided |sf Q|≥ C log n for a suitable constant C. However, despite substantial effort, no polynomial time algorithm is known that succeeds with high probability when |sf Q| = o(√n). Recently Meka and Wigderson citemeka2013association, proposed a method to establish lower bounds within the Sum of Squares (SOS) semidefinite hierarchy. Here we consider the degree-4 SOS relaxation, and study the construction of citemeka2013association to prove that SOS fails unless k≥ C, n1/3/log n. An argument presented by Barak implies that this lower bound cannot be substantially improved unless the witness construction is changed in the proof. Our proof uses the moments method to bound the spectrum of a certain random association scheme, i.e. a symmetric random matrix whose rows and columns are indexed by the edges of an Erd"os-Renyi random graph.