Computer Science – Computational Complexity
Scientific paper
2007-01-02
Computer Science
Computational Complexity
Revised version
Scientific paper
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.
No associations
LandOfFree
An algebraic approach to complexity of data stream computations does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.
If you have personal experience with An algebraic approach to complexity of data stream computations, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and An algebraic approach to complexity of data stream computations will most certainly appreciate the feedback.
Profile ID: LFWR-SCP-O-189104