Some Results on Distributed Source Simulation with no Communication We consider the problem of distributed source simulation with no communication, in which Alice and Bob observe sequences Un and Vn respectively, drawn from a joint distribution p_UVotimes n, and wish to locally generate sequences Xn and Yn respectively with a joint distribution that is close (in KL divergence) to p_XYotimes n. We provide a singleletter condition under which such a simulation is asymptotically possible with a vanishing KL divergence. Our condition is nontrivial only in the case where the GacsKorner (GK) common information between U and V is nonzero, and we conjecture that only scalar Markov chains XUVY can be simulated otherwise. Motivated by this conjecture, we further examine the case where both p UV  and p XY  are doubly symmetric binary sources with parameters p, qleq 12 respectively. While it is trivial that in this case pleq q is both necessary and sufficient, we show that when p is close to q then any successful simulation is close to being scalar in the total variation sense.

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.