Streaming Symmetric Norms via Measure Concentration

A long line of research studies the space complexity of estimating a norm l(x) in the data-stream model, i.e., when x is the frequency vector of an input stream which consists of insertions and deletions of n item types.
Restricting attention to norms l (on R^n) that are symmetric, meaning that l is invariant under sign-flips and coordinate-permutations, I will show that the streaming space complexity is essentially determined by the measure-concentration characteristics of l. The same quantity is known to govern many phenomena in high-dimensional spaces, such as large-deviation bounds and the critical dimension in Dvoretzky's Theorem.
The family of symmetric norms contains several well-studied norms, such as all l_p norms, and indeed we provide a new explanation for the disparity in space complexity between p<=2 and p>2. We also obtain bounds for other norms that are useful in applications.
Joint work with Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut, and Lin F. Yang.