  We consider the problem of counting $k$-cliques in $s$-uniform Erdos-Renyi
hypergraphs $G(n,c,s)$ with edge density $c$, and show that its fine-grained
average-case complexity can be based on its worst-case complexity. We prove the
following:
  1. Dense Erdos-Renyi graphs and hypergraphs: Counting $k$-cliques on
$G(n,c,s)$ with $k$ and $c$ constant matches its worst-case time complexity up
to a $\mathrm{polylog}(n)$ factor. Assuming randomized ETH, it takes
$n^{\Omega(k)}$ time to count $k$-cliques in $G(n,c,s)$ if $k$ and $c$ are
constant.
  2. Sparse Erdos-Renyi graphs and hypergraphs: When $c = \Theta(n^{-\alpha})$,
we give several algorithms exploiting the sparsity of $G(n, c, s)$ that are
faster than the best known worst-case algorithms. Complementing this, based on
a fine-grained worst-case assumption, our results imply a different
average-case phase diagram for each fixed $\alpha$ depicting a tradeoff between
a runtime lower bound and $k$. Surprisingly, in the hypergraph case ($s \ge
3$), these lower bounds are tight against our algorithms exactly when $c$ is
above the Erd\H{o}s-R\'{e}nyi $k$-clique percolation threshold.
  This is the first worst-case-to-average-case hardness reduction for a problem
on Erd\H{o}s-R\'{e}nyi hypergraphs that we are aware of. We also give a variant
of our result for computing the parity of the $k$-clique count that tolerates
higher error probability.
