  The following question arises naturally in the study of graph streaming
algorithms:
  "Is there any graph problem which is "not too hard", in that it can be solved
efficiently with total communication (nearly) linear in the number $n$ of
vertices, and for which, nonetheless, any streaming algorithm with
$\tilde{O}(n)$ space (i.e., a semi-streaming algorithm) needs a polynomial
$n^{\Omega(1)}$ number of passes?"
  Assadi, Chen, and Khanna [STOC 2019] were the first to prove that this is
indeed the case. However, the lower bounds that they obtained are for rather
non-standard graph problems.
  Our first main contribution is to present the first polynomial-pass lower
bounds for natural "not too hard" graph problems studied previously in the
streaming model: $k$-cores and degeneracy. We devise a novel communication
protocol for both problems with near-linear communication, thus showing that
$k$-cores and degeneracy are natural examples of "not too hard" problems.
Indeed, previous work have developed single-pass semi-streaming algorithms for
approximating these problems. In contrast, we prove that any semi-streaming
algorithm for exactly solving these problems requires (almost)
$\Omega(n^{1/3})$ passes.
  Our second main contribution is improved round-communication lower bounds for
the underlying communication problems at the basis of these reductions:
  * We improve the previous lower bound of Assadi, Chen, and Khanna for hidden
pointer chasing (HPC) to achieve optimal bounds.
  * We observe that all current reductions from HPC can also work with a
generalized version of this problem that we call MultiHPC, and prove an even
stronger and optimal lower bound for this generalization.
  These two results collectively allow us to improve the resulting pass lower
bounds for semi-streaming algorithms by a polynomial factor, namely, from
$n^{1/5}$ to $n^{1/3}$ passes.
