# The Landscape of the Planted Clique Problem: Dense subgraphs and the Overlap Gap Property

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

## Key facts

- Cited by 9 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 15 Apr 2019.

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

- [The Franz-Parisi Criterion and Computational Trade-offs in High Dimensional Statistics](https://mlsanity.com/paper/2205.09727/) (2022)
- [On the Cryptographic Hardness of Learning Single Periodic Neurons](https://mlsanity.com/paper/2106.10744/) (2021)
- [The Algorithmic Phase Transition of Random k-SAT for Low Degree Polynomials](https://mlsanity.com/paper/2106.02129/) (2021)
- [On free energy barriers in Gaussian priors and failure of cold start MCMC for high-dimensional unimodal distributions](https://mlsanity.com/paper/2209.02001/) (2022)
- [Average-Case Complexity of Tensor Decomposition for Low-Degree Polynomials](https://mlsanity.com/paper/2211.05274/) (2022)
- [Low coordinate degree algorithms I: Universality of computational thresholds for hypothesis testing](https://mlsanity.com/paper/2403.07862/) (2024)
- [The graph alignment problem: fundamental limits and efficient algorithms](https://mlsanity.com/paper/2404.12418/) (2024)
- [Planted Dense Subgraphs in Dense Random Graphs Can Be Recovered using Graph-based Machine Learning](https://mlsanity.com/paper/2201.01825/) (2022)
- [A short review on the maximum clique problem algorithms with classical, AI, and quantum methods](https://mlsanity.com/paper/2403.09742/) (2024)

## Abstract (arXiv)

In this paper we study the computational-statistical gap of the planted clique problem, where a clique of size k is planted in an Erdos Renyi graph G(n,frac12) resulting in a graph Gleft(n,frac12,kright). The goal is to recover the planted clique vertices by observing Gleft(n,frac12,kright) . It is known that the clique can be recovered as long as k ≥ left(2+εright)log n  for any ε>0, but no polynomial-time algorithm is known for this task unless k=Omegaleft(√n right). Following a statistical-physics inspired point of view as an attempt to understand this computational-statistical gap, we study the landscape of the "sufficiently dense" subgraphs of G and their overlap with the planted clique. Using the first moment method, we study the densest subgraph problems for subgraphs with fixed, but arbitrary, overlap size with the planted clique, and provide evidence of a phase transition for the presence of Overlap Gap Property (OGP) at k=Thetaleft(√nright). OGP is a concept introduced originally in spin glass theory and known to suggest algorithmic hardness when it appears. We establish the presence of OGP when k is a small positive power of n by using a conditional second moment method. As our main technical tool, we establish the first, to the best of our knowledge, concentration results for the K-densest subgraph problem for the Erdos-Renyi model Gleft(n,frac12right) when K=n0.5-ε for arbitrary ε>0. Finally, to study the OGP we employ a certain form of overparametrization, which is conceptually aligned with a large body of recent work in learning theory and optimization.