A Compact RankSelect Data Structure for the Streaming Model For a sorted set S from a universe 1.u received under the streaming model (i.e., elements are received one at a time, in sorted order), such that at a given time it contains n elements x 1 , xe2x80xa6, x n , and whose characteristic bit vector is  C_S0sigma_111cdots 10sigma_211cdots 1cdots 0sigma_g11cdots 1  (i.e., the set elements are actually arranged in g xe2x89xa4 n intervals of size xe2x89xa5 1), we propose a compact data structure that answers operations select and rank in  Theta(mathrmlg(qmathrmlg q) ) worstcase time, and append in  O(1)  amortized time, using  2q mathrmlg fracunaq mathrmlg fracnao(q mathrmlgquad mathrmlg q)  bits of space. The structure is suitable in cases where g  q  .

Towards Optimal Moment Estimation in Streaming and Distributed Models One of the oldest problems in the data stream model is to approximate the pth moment mathcalX_pp  sum_i1n mathcalX_ip of an underlying vector mathcalX in mathbbRn, 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(epsilon2 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(epsilon2 log n) bits, while the lower bound is only Omega(epsilon2  log n) bits. Recently, an upper bound of tildeO(epsilon2  log n) bits was obtained assuming that the updates arrive in a random order.  :126,show that for p in (0, 1, the random order assumption is not needed. Namely, we give an upper bound for worstcase streams of tildeO(epsilon2  log n) bits for estimating mathcalX_pp. Our techniques also give new upper bounds for estimating the empirical entropy in a stream. On the other hand, we :126,show that for p in (1,2, in the natural coordinator and blackboard communication topologies, there is an tildeO(epsilon2) bit maxcommunication 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 tildeO(epsilon2 log d) maxcommunication upper bound, where d is the diameter of G. Interestingly, our upper bound rules out natural communication complexitybased approaches for proving an Omega(epsilon2 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.