Streaming Symmetric Norms via Measure Concentration

Jaroslaw Blasiok, Vladimir Braverman, Stephen R. Chestnut +2

We characterize the streaming space complexity of every symmetric norm $l$ (a norm on ${\mathbb{R}}^n$ invariant under sign-flips and coordinate-permutations), by relating this space…