Before revision: We study the classical problem of moment estimation of an underlying vector whose n coordinates are implicitly defined through a series of updates in a data stream. We show that if the updates to the vector arrive in the random-order insertion-only model , then there exist space efficient algorithms with improved dependencies on the approximation parameter \varepsilon .
After revision: In the adversarially robust streaming model, a stream of elements is presented to an algorithm and is allowed to depend on the output of the algorithm at earlier times during the stream. In the classic insertion-only model , then there exist space efficient algorithms with improved dependencies on the approximation parameter \varepsilon .