Version 6 changes:
-----------------
-- More or less the final journal version. (2/5/2014)
-- Fixed minor typos. (2/5/2014)
-- Added Remark 23 explaining connection to sparse oblivious subspace
embeddings.
-----------------
Version 5 changes:
-----------------
-- Modified the abstract and fixed some typos. (8/21/2013)
-- Added an open problems section at end of paper. (8/21/2013)
-----------------
Version 4 changes:
-----------------
-- Simplified section 4 by giving 1 analysis that covers both
constructions. Also fixed some minor typos. (12/7/2012)
-----------------
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)