# Low-degree phase transitions for detecting a planted clique in sublinear time

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 20 of its 55 references that are in the map.
- First posted on arXiv 8 Feb 2024.

## Builds on (most cited first, 20 of 20)

- [Notes on Computational Hardness of Hypothesis Testing: Predictions using the Low-Degree Likelihood Ratio](https://mlsanity.com/paper/1907.11636/) (2019)
- [A statistical model for tensor PCA](https://mlsanity.com/paper/1411.1076/) (2014)
- [The power of sum-of-squares for detecting hidden structures](https://mlsanity.com/paper/1710.05017/) (2017)
- [Subexponential-Time Algorithms for Sparse PCA](https://mlsanity.com/paper/1907.11635/) (2019)
- [Computational Barriers to Estimation from Low-Degree Polynomials](https://mlsanity.com/paper/2008.02269/) (2020)
- [Reducibility and Computational Lower Bounds for Problems with Planted Sparse Structure](https://mlsanity.com/paper/1806.07508/) (2018)
- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [Bayesian estimation from few samples: community detection and related problems](https://mlsanity.com/paper/1710.00264/) (2017)
- [Local Statistics, Semidefinite Programming, and Community Detection](https://mlsanity.com/paper/1911.01960/) (2019)
- [Spectral Planting and the Hardness of Refuting Cuts, Colorability, and Communities in Random Graphs](https://mlsanity.com/paper/2008.12237/) (2020)
- [Low-Degree Hardness of Detection for Correlated ErdHos-R'enyi Graphs](https://mlsanity.com/paper/2311.15931/) (2023)
- [Statistical and Computational Phase Transitions in Group Testing](https://mlsanity.com/paper/2206.07640/) (2022)
- [Detection of Dense Subhypergraphs by Low-Degree Polynomials](https://mlsanity.com/paper/2304.08135/) (2023)
- [Finding a planted clique by adaptive probing](https://mlsanity.com/paper/1903.12050/) (2019)
- [Average-Case Communication Complexity of Statistical Problems](https://mlsanity.com/paper/2107.01335/) (2021)
- [Finding Planted Cliques in Sublinear Time](https://mlsanity.com/paper/2004.12002/) (2020)
- [The Average-Case Complexity of Counting Cliques in Erdos-Renyi Hypergraphs](https://mlsanity.com/paper/1903.08247/) (2019)
- [Random Subgraph Detection Using Queries](https://mlsanity.com/paper/2110.00744/) (2021)
- [A tight bound for the clique query problem in two rounds](https://mlsanity.com/paper/2112.06072/) (2021)
- [New Techniques for Proving Fine-Grained Average-Case Hardness](https://mlsanity.com/paper/2008.06591/) (2020)

## Abstract (arXiv)

We consider the problem of detecting a planted clique of size k in a random graph on n vertices. When the size of the clique exceeds Theta(√n), polynomial-time algorithms for detection proliferate. We study faster -- namely, sublinear time -- algorithms in the high-signal regime when k = Theta(n1/2 + δ), for some δ > 0. To this end, we consider algorithms that non-adaptively query a subset M of entries of the adjacency matrix and then compute a low-degree polynomial function of the revealed entries. We prove a computational phase transition for this class of non-adaptive low-degree algorithms: under the scaling lvert M rvert = Theta(nγ), the clique can be detected when γ > 3(1/2 - δ) but not when γ < 3(1/2 - δ). As a result, the best known runtime for detecting a planted clique, widetildeO(n3(1/2-δ)), cannot be improved without looking beyond the non-adaptive low-degree class. Our proof of the lower bound -- based on bounding the conditional low-degree likelihood ratio -- reveals further structure in non-adaptive detection of a planted clique. Using (a bound on) the conditional low-degree likelihood ratio as a potential function, we show that for every non-adaptive query pattern, there is a highly structured query pattern of the same size that is at least as effective.