The Landscape of the Planted Clique Problem: Dense subgraphs and the
  Overlap Gap Property
  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,\frac{1}{2})$ resulting in a graph $G\left(n,\frac{1}{2},k\right)$. The
goal is to recover the planted clique vertices by observing
$G\left(n,\frac{1}{2},k\right)$ . It is known that the clique can be recovered
as long as $k \geq \left(2+\epsilon\right)\log n $ for any $\epsilon>0$, but no
polynomial-time algorithm is known for this task unless $k=\Omega\left(\sqrt{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=\Theta\left(\sqrt{n}\right)$. 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
$G\left(n,\frac{1}{2}\right)$ when $K=n^{0.5-\epsilon}$ for arbitrary
$\epsilon>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.
