Revisiting the direct sum theorem and space lower bounds in random order streams

Abstract

Estimating frequency moments and L p distances are well studied problems in the adversarial data stream model and tight space bounds are known for these two problems. There has been growing interest in revisiting these problems in the framework of random-order streams. The best space lower bound known for computing the k th frequency moment in random-order streams is Ω(n 1-2.5/k ) by Andoni et al., and it is conjectured that the real lower bound shall be Ω(n 1-2/k ). In this paper, we resolve this conjecture. In our approach, we revisit the direct sum theorem developed by Bar-Yossef et al. in a random-partition private messages model and provide a tight Ω(n 1-2/k /ℓ) space lower bound for any ℓ-pass algorithm that approximates the frequency moment in random-order stream model to a constant factor. Finally, we also introduce the notion of space-entropy tradeoffs in random order streams, as a means of studying intermediate models between adversarial and fully random order streams. We show an almost tight space-entropy tradeoff for L ∞ distance and a non-trivial tradeoff for L p distances. © 2009 Springer Berlin Heidelberg.