  We formulate a new hardness assumption, the Strongish Planted Clique
Hypothesis (SPCH), which postulates that any algorithm for planted clique must
run in time $n^{\Omega(\log{n})}$ (so that the state-of-the-art running time of
$n^{O(\log n)}$ is optimal up to a constant in the exponent).
  We provide two sets of applications of the new hypothesis. First, we show
that SPCH implies (nearly) tight inapproximability results for the following
well-studied problems in terms of the parameter $k$: Densest $k$-Subgraph,
Smallest $k$-Edge Subgraph, Densest $k$-Subhypergraph, Steiner $k$-Forest, and
Directed Steiner Network with $k$ terminal pairs. For example, we show, under
SPCH, that no polynomial time algorithm achieves $o(k)$-approximation for
Densest $k$-Subgraph. This inapproximability ratio improves upon the previous
best $k^{o(1)}$ factor from (Chalermsook et al., FOCS 2017). Furthermore, our
lower bounds hold even against fixed-parameter tractable algorithms with
parameter $k$.
  Our second application focuses on the complexity of graph pattern detection.
For both induced and non-induced graph pattern detection, we prove hardness
results under SPCH, which improves the running time lower bounds obtained by
(Dalirrooyfard et al., STOC 2019) under the Exponential Time Hypothesis.
