An algebraic approach to complexity of data stream computations

Sumit Ganguly

We consider a basic problem in the general data streaming model, namely, to estimate a vector $f\in {\mathbb{Z}}^n$ that is arbitrarily updated (i.e., incremented or decremented) coordinate…