  The log-density method is a powerful algorithmic framework which in recent
years has given rise to the best-known approximations for a variety of
problems, including Densest-$k$-Subgraph and Bipartite Small Set Vertex
Expansion. These approximations have been conjectured to be optimal based on
various instantiations of a general conjecture: that it is hard to distinguish
a fully random combinatorial structure from one which contains a similar
planted sub-structure with the same "log-density".
  We bolster this conjecture by showing that in a random hypergraph with edge
probability $n^{-\alpha}$, $\tilde\Omega(\log n)$ rounds of Sherali-Adams with
cannot rule out the existence of a $k$-subhypergraph with edge density
$k^{-\alpha-o(1)}$, for any $k$ and $\alpha$. This holds even when the bound on
the objective function is lifted. This gives strong integrality gaps which
exactly match the gap in the above distinguishing problems, as well as the
best-known approximations, for Densest $k$-Subgraph, Smallest $p$-Edge
Subgraph, their hypergraph extensions, and Small Set Bipartite Vertex Expansion
(or equivalently, Minimum $p$-Union). Previously, such integrality gaps were
known only for Densest $k$-Subgraph for one specific parameter setting.
