  The densest k-subgraph (DkS) problem (i.e. find a size k subgraph with
maximum number of edges), is one of the notorious problems in approximation
algorithms. There is a significant gap between known upper and lower bounds for
DkS: the current best algorithm gives an ~ O(n^{1/4}) approximation, while even
showing a small constant factor hardness requires significantly stronger
assumptions than P != NP. In addition to interest in designing better
algorithms, a number of recent results have exploited the conjectured hardness
of densest k-subgraph and its variants. Thus, understanding the approximability
of DkS is an important challenge.
  In this work, we give evidence for the hardness of approximating DkS within
polynomial factors. Specifically, we expose the limitations of strong
semidefinite programs from SDP hierarchies in solving densest k-subgraph. Our
results include:
  * A lower bound of Omega(n^{1/4}/log^3 n) on the integrality gap for
Omega(log n/log log n) rounds of the Sherali-Adams relaxation for DkS. This
also holds for the relaxation obtained from Sherali-Adams with an added SDP
constraint. Our gap instances are in fact Erdos-Renyi random graphs.
  * For every epsilon > 0, a lower bound of n^{2/53-eps} on the integrality gap
of n^{Omega(eps)} rounds of the Lasserre SDP relaxation for DkS, and an
n^{Omega_eps(1)} gap for n^{1-eps} rounds. Our construction proceeds via a
reduction from random instances of a certain Max-CSP over large domains.
  In the absence of inapproximability results for DkS, our results show that
even the most powerful SDPs are unable to beat a factor of n^{Omega(1)}, and in
fact even improving the best known n^{1/4} factor is a barrier for current
techniques.
