Version 3 changes:
-----------------
-- Fixed some errors in the version 2 writeup of the proof of Theorem
25. The theorem conclusion is unchanged. In particular, the v2
proof took q = Theta(log(1/delta)/log(1/eps)) in the case s =
Omega(1/eps) and looked at q items colliding. This makes no sense
if q > s (which can happen depending on the relationship between
eps, delta). Really one should take q = Theta(sqrt(eps*s)), which
is Theta(log(1/delta)/log(1/eps)) for the largest setting of s, but
not always. See the version 3 paper for details. (4/28/2011)
-----------------
Version 2 changes:
-----------------
-- Showed that the construction of [Dasgupta-Kumar-Sarlos, STOC 2010]
requires sparsity Omega~(eps^{-1} * log^2(1/delta)). (4/14/2011)
-- Gave a second new construction which achieves sparsity Theta(eps^{-1} *
log(1/delta)). (4/14/2011)
-- Changed the title to "Sparser Johnson-Lindenstrauss Transforms", since
we now give two constructions. (4/14/2011)