David P. Woodruff

One of the oldest problems in the data stream model is to approximate the p th moment \(\Vert \mathbf {X}\Vert _p^p = \sum _{i=1}^n \mathbf {X}_i^p\) of an underlying non-negative vector \(\mathbf {X}\in \mathbb {R}^n\) , which is presented as a sequence of \(\mathrm{poly}(n)\) updates to its coordinates. Of particular interest is when \(p \in (0,2]\) . Although a tight space bound of \(\Theta (\epsilon ^{-2} \log n)\) bits is known for this problem when both positive and negative updates are allowed, surprisingly, there is still a gap in the space complexity of this problem when all updates are positive. Specifically, the upper bound is \(O(\epsilon ^{-2} \log n)\) bits, while the lower bound is only \(\Omega (\epsilon ^{-2} + \log n)\) bits. Recently, an upper bound of \(\tilde{O}(\epsilon ^{-2} + \log n)\) bits was obtained under the assumption that the updates arrive in a random order . We show that for \(p \in (0, 1]\) , the random order assumption is not needed. Namely, we give an upper bound for worst-case streams of \(\tilde{O}(\epsilon ^{-2} + \log n)\) bits for estimating \(\Vert \mathbf {X}\Vert _p^p\) . Our techniques also give new upper bounds for estimating the empirical entropy in a stream. However, we show that for \(p \in (1,2]\) , in the natural coordinator and blackboard distributed communication topologies, there is an \(\tilde{O}(\epsilon ^{-2})\) bit max-communication upper bo