Paper Info
Title
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.
Year
DOI
Venue
2013
10.1109/ITW.2013.6691324
Information Theory Workshop
Keywords
Field
DocType
communication complexity,estimation theory,interpolation,cascaded norm estimation problem,classical norm estimation problem,communication protocols,data stream problem,information complexity paradigm,key negative-type inequalities,transcript distributions
Discrete mathematics,Computer science,Data stream,Norm (social),Theoretical computer science,Information complexity,Communications protocol,Sketch
Conference
ISBN
Citations 
PageRank 
978-1-4799-1321-3
1
0.35
References 
Authors
13
1
Name
Order
Citations
PageRank
T. S. Jayram1137375.87