Kane, Daniel M.Nelson, Jelani2017-10-272010Kane, Daniel M. and Nelson, Jelani. 2010. "A Derandomized Sparse Johnson-Lindenstrauss Transform." Working paper.http://nrs.harvard.edu/urn-3:HUL.InstRepos:34305998Recent work of [Dasgupta-Kumar-Sarl´os, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently derandomized. We answer their question affirmatively by giving an alternative proof of their result requiring only bounded independence hash functions. Furthermore, the sparsity bound obtained in our proof is improved. Our work implies the first implementation of a JohnsonLindenstrauss transform in data streams with sublinear update time.en-USResearch Paper or Report2015-01-13Daniel M. Kane, Jelani Nelson2017-10-27