2007/01/02 by Šumit Ganguly, Sumit Ganguly, Ganguly, Sumit
Computer Science · #Algorithms and Data Compression #Complexity and Algorithms in Graphs #Computational Complexity (cs.CC) #Cryptography and Data Security #FOS: Computer and information sciences #cs.CC
paper · pdf · doi:10.48550/arxiv.cs/0701004
Revised version
openalex publication_date 2007/01/02 · arxiv created 2008/04/06 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
We consider a basic problem in the general data streaming model, namely, to estimate a vector f ∈ \Zn that is arbitrarily updated (i.e., incremented or decremented) coordinate-wise. The estimate f ∈ \Zn must satisfy \normf-f∞≤ ε\normf1 , that is, ∀ i ~(\absfi - fi ≤ ε\normf1). It is known to have O(ε-1) randomized space upper bound \citecm:jalgo, Ω(ε-1 log (εn)) space lower bound \citebkmt:sirocco03 and deterministic space upper bound of Ω(ε-2) bits.\footnoteThe O and Ω notations suppress poly-logarithmic factors in n, log ε-1, \normf∞ and log δ-1, where, δ is the error probability (for randomized algorithm). We show that any deterministic algorithm for this problem requires space Ω(ε-2 (log \normf1)) bits.