An algebraic approach to complexity of data stream computations
| dc.creator | Ganguly, Sumit | |
| dc.date | 2007-01-02 | |
| dc.date | 2008-04-06 | |
| dc.date.accessioned | 2026-07-07T09:30:33Z | |
| dc.date.available | 2026-07-07T09:30:33Z | |
| dc.description | 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 ε\norm{f}_1 $, that is, $\forall i ~(\abs{\hat{f}_i - f_i} \le ε\norm{f}_1)$. It is known to have $\tilde{O}(ε^{-1})$ randomized space upper bound \cite{cm:jalgo}, $Ω(ε^{-1} \log (εn))$ space lower bound \cite{bkmt:sirocco03} and deterministic space upper bound of $\tildeΩ(ε^{-2})$ bits.\footnote{The $\tilde{O}$ and $\tildeΩ$ notations suppress poly-logarithmic factors in $n, \log ε^{-1}, \norm{f}_{\infty}$ and $\log δ^{-1}$, where, $δ$ is the error probability (for randomized algorithm).} We show that any deterministic algorithm for this problem requires space $Ω(ε^{-2} (\log \norm{f}_1))$ bits. | |
| dc.description | Revised version | |
| dc.identifier | https://arxiv.org/abs/cs/0701004 | |
| dc.identifier | http://arxiv.org/abs/cs/0701004 | |
| dc.identifier.uri | http://salesiana.dossiersoluciones.com/handle/123456789/158157 | |
| dc.subject | Computational Complexity | |
| dc.title | An algebraic approach to complexity of data stream computations | |
| dc.type | text |