  One of the oldest problems in the data stream model is to approximate the
$p$-th moment $\|\mathcal{X}\|_p^p = \sum_{i=1}^n |\mathcal{X}_i|^p$ of an
underlying vector $\mathcal{X} \in \mathbb{R}^n$, which is presented as a
sequence of 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 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 assuming 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 $\|\mathcal{X}\|_p^p$.
Our techniques also give new upper bounds for estimating the empirical entropy
in a stream. On the other hand, we show that for $p \in (1,2]$, in the natural
coordinator and blackboard communication topologies, there is an
$\tilde{O}(\epsilon^{-2})$ bit max-communication upper bound based on a
randomized rounding scheme. Our protocols also give rise to protocols for heavy
hitters and approximate matrix product. We generalize our results to arbitrary
communication topologies $G$, obtaining an $\tilde{O}(\epsilon^{2} \log d)$
max-communication upper bound, where $d$ is the diameter of $G$. Interestingly,
our upper bound rules out natural communication complexity-based approaches for
proving an $\Omega(\epsilon^{-2} \log n)$ bit lower bound for $p \in (1,2]$ for
streaming algorithms. In particular, any such lower bound must come from a
topology with large diameter.
