On the information complexity of cascaded norms with small domains

Abstract

We consider the problem of estimating cascaded norms in a data stream, a well-studied generalization of the classical norm estimation problem, where the data is aggregated in a cascaded fashion along multiple attributes. We show that when the number of attributes for each item is at most d, then estimating the cascaded norm Lk○L1 requires space Ω(d·n1-2/k) for every d = O(n1/k). This result interpolates between the tight lower bounds known previously for the two extremes of d = 1 and d = Θ(n1/k) [1]. The proof of this result uses the information complexity paradigm that has proved successful in obtaining tight lower bounds for several well-known problems. We use the above data stream problem as a motivation to sketch some of the key ideas of this paradigm. In particular, we give a unified and a more general view of the key negative-type inequalities satisfied by the transcript distributions of communication protocols. © 2013 IEEE.