  We study space-pass tradeoffs in graph streaming algorithms for parameter
estimation and property testing problems such as estimating the size of maximum
matchings and maximum cuts, weight of minimum spanning trees, or testing if a
graph is connected or cycle-free versus being far from these properties. We
develop a new lower bound technique that proves that for many problems of
interest, including all the above, obtaining a $(1+\epsilon)$-approximation
requires either $n^{\Omega(1)}$ space or $\Omega(1/\epsilon)$ passes, even on
highly restricted families of graphs such as bounded-degree planar graphs. For
multiple of these problems, this bound matches those of existing algorithms and
is thus (asymptotically) optimal.
  Our results considerably strengthen prior lower bounds even for arbitrary
graphs: starting from the influential work of [Verbin, Yu; SODA 2011], there
has been a plethora of lower bounds for single-pass algorithms for these
problems; however, the only multi-pass lower bounds proven very recently in
[Assadi, Kol, Saxena, Yu; FOCS 2020] rules out sublinear-space algorithms with
exponentially smaller $o(\log{(1/\epsilon)})$ passes for these problems.
  One key ingredient of our proofs is a simple streaming XOR Lemma, a generic
hardness amplification result, that we prove: informally speaking, if a
$p$-pass $s$-space streaming algorithm can only solve a decision problem with
advantage $\delta > 0$ over random guessing, then it cannot solve XOR of $\ell$
independent copies of the problem with advantage much better than
$\delta^{\ell}$. This result can be of independent interest and useful for
other streaming lower bounds as well.
