The densest k-subgraph (DkS) problem, where given a graph and integer k, the goal is to find the subgraph on k vertices having the maximum number of edges, is one of the notorious problems in approximation algorithms. While the problem has frustrated the development of good approximation algorithms, inapproximability results have also been hard to come by ( it is NP-hard, and does not have a PTAS unless NP has subexponential time algorithms). Adding to the interest in studying this problem are a number of recent results which have exploited the conjectured hardness of densest $k$-subgraph and its variants.

This talk will cover some recent developments in the last couple of years, about the use of LP and SDP hierarchies to obtain better approximation algorithms for the problem. I will primarily focus on an

algorithm which gives an O(n^{1/4 + \epsilon}) factor approximation, by considering O(1/\epsilon) levels of an LP hierarchy. This worst-case algorithm is, in fact, inspired by studying a planted version of the problem. Moreover, these instances also seem to present a barrier to further progress.