Pseudodeterministic Streaming A pseudodeterministic algorithm is a (randomized) algorithm which, when run multiple times on the same input, with high probability outputs the same result on all executions. Classic streaming algorithms, such as those for finding heavy hitters, approximate counting, ell_2 approximation, finding a nonzero entry in a vector (for turnstile algorithms) are not pseudodeterministic. For example, in the instance of finding a nonzero entry in a vector, for any known lowspace algorithm A, there exists a stream x so that running A twice on x (using different randomness) would with high probability result in two different entries as the output.  :99,this work, we study whether it is inherent that these algorithms output different values on different executions. That is, we ask whether these problems have lowmemory pseudodeterministic algorithms. For instance, we show that there is no lowmemory pseudodeterministic algorithm for finding a nonzero entry in a vector (given in a turnstile fashion), and also that there is no lowdimensional pseudodeterministic sketching algorithm for ell_2 norm estimation. We also exhibit problems which do have low memory pseudodeterministic algorithms but no low memory deterministic algorithm, such as outputting a nonzero row of a matrix, or outputting a basis for the rowspan of a matrix.  also :202,investigate multipseudodeterministic algorithms: algorithms which with high probability output one of a few options. We show the first lower bounds for such algorithms. This implies that there are streaming problems such that every low space algorithm for the problem must have inputs where there are many valid outputs, all with a significant probability of being outputted.

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.