We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v\succeq u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. The function F is generally non-linear, and we give the first difference estimators for the frequency moments F_p for p\in[0,2], as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models. For adversarially robust streams, we obtain a (1+\epsilon)-approximation to F_p using%DIFDELCMD < \mathcal{O}\left(%%% \frac{\log n{\epsilon^2}}%DIFDELCMD < \right) %%% bits of space for p\in[0,2] and using%DIFDELCMD < \mathcal{O}\left(%%% \frac{1{\epsilon^2}n^{1-2/p}}%DIFDELCMD < \right) %%% bits of space for integers p>2.
<meaning-changed> We introduce difference estimators for data stream computation, which provide approximations to F(v)-F(u) for frequency vectors v\succeq u and a given function F. We show how to use such estimators to carefully trade error for memory in an iterative manner. The function F is generally non-linear, and we give the first difference estimators for the frequency moments F_p for p\in[0,2], as well as for integers p>2. Using these, we resolve a number of central open questions in adversarial robust streaming and sliding window models. For adversarially robust streams, we obtain a (1+\epsilon)-approximation to F_p using%DIFDELCMD < \mathcal{O}\left(%%% \frac{\log n{\epsilon^2}}%DIFDELCMD < \right) %%% bits of space for p\in[0,2] and using%DIFDELCMD < \mathcal{O}\left(%%% \frac{1{\epsilon^2}n^{1-2/p}}%DIFDELCMD < \right) %%% bits of space for integers p>2.
%DIFDELCMD < \mathcal{O}\left(%%% \frac{\log n{\epsilon^2}}%DIFDELCMD < \right) %%% bits of space for p\in[0,2] and using%DIFDELCMD < \mathcal{O}\left(%%% \frac{1{\epsilon^2}n^{1-2/p}}%DIFDELCMD < \right) %%% bits of space for integers p>2.