  Given a graph and an integer $k$, Densest $k$-Subgraph is the algorithmic
task of finding the subgraph on $k$ vertices with the maximum number of edges.
This is a fundamental problem that has been subject to intense study for
decades, with applications spanning a wide variety of fields. The
state-of-the-art algorithm is an $O(n^{1/4 + \epsilon})$-factor approximation
(for any $\epsilon > 0$) due to Bhaskara et al. [STOC '10]. Moreover, the
so-called log-density framework predicts that this is optimal, i.e. it is
impossible for an efficient algorithm to achieve an $O(n^{1/4 -
\epsilon})$-factor approximation. In the average case, Densest $k$-Subgraph is
a prototypical noisy inference task which is conjectured to exhibit a
statistical-computational gap.
  In this work, we provide the strongest evidence yet of hardness for Densest
$k$-Subgraph by showing matching lower bounds against the powerful
Sum-of-Squares (SoS) algorithm, a meta-algorithm based on convex programming
that achieves state-of-art algorithmic guarantees for many optimization and
inference problems. For $k \leq n^{\frac{1}{2}}$, we obtain a degree
$n^{\delta}$ SoS lower bound for the hard regime as predicted by the
log-density framework.
  To show this, we utilize the modern framework for proving SoS lower bounds on
average-case problems pioneered by Barak et al. [FOCS '16]. A key issue is that
small denser-than-average subgraphs in the input will greatly affect the value
of the candidate pseudoexpectation operator around the subgraph. To handle this
challenge, we devise a novel matrix factorization scheme based on the positive
minimum vertex separator. We then prove an intersection tradeoff lemma to show
that the error terms when using this separator are indeed small.
