  In the Densest $k$-Subgraph problem, given an undirected graph $G$ and an
integer $k$, the goal is to find a subgraph of $G$ on $k$ vertices that
contains maximum number of edges. Even though the state-of-the-art algorithm
for the problem achieves only $O(n^{1/4 + \varepsilon})$ approximation ratio
(Bhaskara et al., 2010), previous attempts at proving hardness of
approximation, including those under average case assumptions, fail to achieve
a polynomial ratio; the best ratios ruled out under any worst case assumption
and any average case assumption are only any constant (Raghavendra and Steurer,
2010) and $2^{\Omega(\log^{2/3} n)}$ (Alon et al., 2011) respectively.
  In this work, we show, assuming the exponential time hypothesis (ETH), that
there is no polynomial-time algorithm that approximates Densest $k$-Subgraph to
within $n^{1/(\log \log n)^c}$ factor of the optimum, where $c > 0$ is a
universal constant independent of $n$. In addition, our result has "perfect
completeness", meaning that we prove that it is ETH-hard to even distinguish
between the case in which $G$ contains a $k$-clique and the case in which every
induced $k$-subgraph of $G$ has density at most $1/n^{-1/(\log \log n)^c}$ in
polynomial time.
  Moreover, if we make a stronger assumption that there is some constant
$\varepsilon > 0$ such that no subexponential-time algorithm can distinguish
between a satisfiable 3SAT formula and one which is only $(1 -
\varepsilon)$-satisfiable (also known as Gap-ETH), then the ratio above can be
improved to $n^{f(n)}$ for any function $f$ whose limit is zero as $n$ goes to
infinity (i.e. $f \in o(1)$).
