Stable distributions, pseudorandom generators, embeddings and data stream computation

In this paper we show several results obtained by combining the use of stable distributions with pseudorandom generators for bounded space. In particular: we show how to maintain (using only O(log n/ε²) words of storage) a sketch C(p) of a point p∈l₁ⁿ under dynamic updates of its coordinates, such that given sketches C(p) and C(q) one can estimate |p-q|₁ up to a factor of (1+ε) with large probability. We obtain another sketch function C´ which maps l₁ⁿ into a normed space l₁^m (as opposed to C), such that m=m(n) is much smaller than n; to our knowledge this is the first dimensionality reduction lemma for l₁ norm we give an explicit embedding of l₂ⁿ into l_l^{nO(log n)} with distortion (1+1/n^θ(1)) and a non-constructive embedding of l₂ⁿ into l₁^O(n) with distortion (1+ε) such that the embedding can be represented using only O(n log² n) bits (as opposed to at least n² used by earlier methods)