






















We consider streaming algorithms for approximating a product of input probabilities up to multiplicative error of $1-ε$. It is shown that every randomized streaming algorithm for this problem needs space $Ω(\log n + \log b - \log ε) - \mathcal{O}(1)$, where $n$ is length of the input stream and $b$ is the bit length of the input numbers. This matches an upper bound from Alur et al.~up to a constant multiplicative factor. Moreover, we consider the threshold problem, where it is asked whether the product of the input probabilities is below a given threshold. It is shown that every randomized streaming algorithm for this problem needs space $Ω(n \cdot b)$.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。