Before revision:  Finally, we give an improved lower bound of \Omega \frac{1{\varepsilon^2}\cdot n^{1-2/p}} for one-pass insertion-only streams. Our results separate the complexity of this problem both between random and non-random orders, as well as one-pass and multi-pass streams.
After revision:  Finally, we give an improved lower bound of \Omega \frac{1{\varepsilon^2}\cdot n^{1-2/p}} dependence on the approximation factor. As in previous work, we obtain a general transformation that applies to any non-robust streaming algorithm and depends on the so-called flip number. However, the key technical innovation is that we apply the transformation to what we call a difference estimator for the streaming problem, rather than an estimator for the streaming problem itself. We then develop the first difference estimators for a wide range of problems. Our difference estimator methodology is not only applicable to the adversarially robust model, but to other streaming models where temporal properties of the data play a central role. (Abstract shortened to meet arXiv limit.)