  Adversarially robust streaming algorithms are required to process a stream of
elements and produce correct outputs, even when each stream element can be
chosen as a function of earlier algorithm outputs. As with classic streaming
algorithms, which must only be correct for the worst-case fixed stream,
adversarially robust algorithms with access to randomness can use significantly
less space than deterministic algorithms. We prove that for the Missing Item
Finding problem in streaming, the space complexity also significantly depends
on how adversarially robust algorithms are permitted to use randomness. (In
contrast, the space complexity of classic streaming algorithms does not depend
as strongly on the way randomness is used.)
  For Missing Item Finding on streams of length $\ell$ with elements in
$\{1,\ldots,n\}$, and $\le 1/\text{poly}(\ell)$ error, we show that when $\ell
= O(2^{\sqrt{\log n}})$, "random seed" adversarially robust algorithms, which
only use randomness at initialization, require $\ell^{\Omega(1)}$ bits of
space, while "random tape" adversarially robust algorithms, which may make
random decisions at any time, may use $O(\text{polylog}(\ell))$ space. When
$\ell$ is between $n^{\Omega(1)}$ and $O(\sqrt{n})$, "random tape"
adversarially robust algorithms need $\ell^{\Omega(1)}$ space, while "random
oracle" adversarially robust algorithms, which can read from a long random
string for free, may use $O(\text{polylog}(\ell))$ space. The space lower bound
for the "random seed" case follows, by a reduction given in prior work, from a
lower bound for pseudo-deterministic streaming algorithms given in this paper.
