65 citations · 262 across the 38 of their papers we have counts for
4 papers · 2 filters
Almost Optimal Explicit Johnson-Lindenstrauss Transformations
Raghu Meka
The Johnson-Lindenstrauss lemma is a fundamental result in probability with several applications in the design and analysis of algorithms in high dimensional geometry. Most known c…
Sparser Johnson-Lindenstrauss Transforms
Daniel M. Kane, Jelani Nelson
We give two different and simple constructions for dimensionality reduction in via linear mappings that are sparse: only an -fraction of entries in each co…
Fast Moment Estimation in Data Streams in Optimal Space
Daniel M. Kane, Jelani Nelson, Ely Porat +1
We give a space-optimal algorithm with update time O(log^2(1/eps)loglog(1/eps)) for (1+eps)-approximating the pth frequency moment, 0 < p < 2, of a length-n vector updated in a dat…
A Derandomized Sparse Johnson-Lindenstrauss Transform
Daniel M. Kane, Jelani Nelson
Recent work of [Dasgupta-Kumar-Sarlos, STOC 2010] gave a sparse Johnson-Lindenstrauss transform and left as a main open question whether their construction could be efficiently der…