  We consider a basic problem in the general data streaming model, namely, to
estimate a vector $f \in \Z^n$ that is arbitrarily updated (i.e., incremented
or decremented) coordinate-wise. The estimate $\hat{f} \in \Z^n$ must satisfy
$\norm{\hat{f}-f}_{\infty}\le \epsilon\norm{f}_1 $, that is, $\forall i
~(\abs{\hat{f}_i - f_i} \le \epsilon \norm{f}_1)$. It is known to have
$\tilde{O}(\epsilon^{-1})$ randomized space upper bound \cite{cm:jalgo},
$\Omega(\epsilon^{-1} \log (\epsilon n))$ space lower bound
\cite{bkmt:sirocco03} and deterministic space upper bound of
$\tilde{\Omega}(\epsilon^{-2})$ bits.\footnote{The $\tilde{O}$ and
$\tilde{\Omega}$ notations suppress poly-logarithmic factors in $n, \log
\epsilon^{-1}, \norm{f}_{\infty}$ and $\log \delta^{-1}$, where, $\delta$ is
the error probability (for randomized algorithm).} We show that any
deterministic algorithm for this problem requires space $\Omega(\epsilon^{-2}
(\log \norm{f}_1))$ bits.
