Fetching the paper…
Reading the bibliography…
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 derandomized.
A bound on tail probabilities for quadratic forms in independent random variables
David Lee Hanson and Farroll Tim Wright · 1971
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
William B. Johnson and Joram Lindenstrauss · 1984
Earlier work this paper cites.
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
Peter Frankl and Hiroshi Maehara · 1988
Earlier work this paper cites.
Pseudorandom generators for space-bounded computation
Noam Nisan · 1992
Earlier work this paper cites.
Approximate nearest neighbors: Towards removing the curse of dimensionality
Piotr Indyk and Rajeev Motwani · 1998
Earlier work this paper cites.
The Space Complexity of Approximating the Frequency Moments
Noga Alon, Yossi Matias, and Mario Szegedy · 1999
Earlier work this paper cites.
Modern Computer Algebra
Joachim von zur Gathen and Jürgen Gerhard · 1999
Earlier work this paper cites.
The Probabilistic Method
Noga Alon and Joel H. Spencer · 2000
Earlier work this paper cites.
Finding frequent items in data streams
Moses Charikar, Kevin Chen, and Martin Farach-Colton · 2002
Earlier work this paper cites.
Derandomized dimensionality reduction with applications
Lars Engebretsen, Piotr Indyk, and Ryan O’Donnell · 2002
Earlier work this paper cites.
Algorithmic derandomization via complexity theory
D. Sivakumar · 2002
Earlier work this paper cites.
Database-friendly random projections: Johnson-Lindenstrauss with binary coins
Dimitris Achlioptas · 2003
Cited alongside, same era.
An elementary proof of a theorem of Johnson and Lindenstrauss
Sanjoy Dasgupta and Anupam Gupta · 2003
Cited alongside, same era.
Tabulation based 4-universal hashing with applications to second moment estimation
Mikkel Thorup and Yin Zhang · 2004
Cited alongside, same era.
Data Streams: Algorithms and Applications
S. Muthukrishnan · 2005
Cited alongside, same era.
Approximate nearest neighbors and the fast Johnson-Lindenstrauss transform
Nir Ailon and Bernard Chazelle · 2006
Cited alongside, same era.
An algorithmic theory of learning: Robust concepts and random projection
Rosa I. Arriaga and Santosh Vempala · 2006
Cited alongside, same era.
Explicit dimension reduction and its applications
Zohar Karnin, Yuval Rabani, and Amir Shpilka · 2009
Later among the works it cites.
A sparse Johnson-Lindenstrauss transform
Anirban Dasgupta, Ravi Kumar, and Tamás Sarlós · 2010
Closest in time.
Bounded independence fools degree-2 threshold functions
Ilias Diakonikolas, Daniel M. Kane, and Jelani Nelson · 2010
Closest in time.
Johnson-Lindenstrauss lemma for circulant matrices
Aicke Hinrichs and Jan Vybíral · 2010
Closest in time.
New and improved Johnson-Lindenstrauss embeddings via the Restricted Isometry Property
Felix Krahmer and Rachel Ward · 2010
Closest in time.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Stable distributions, pseudorandom generators, embeddings, and data stream computation
Piotr Indyk · 2006
Cited alongside, same era.
Dense fast random projections and Lean Walsh transforms
Edo Liberty, Nir Ailon, and Amit Singer · 2008
Cited alongside, same era.
On variants of the Johnson-Lindenstrauss lemma
Jirí Matousek · 2008
Cited alongside, same era.
Fast dimension reduction using Rademacher series on dual BCH codes
Nir Ailon and Edo Liberty · 2009
Cited alongside, same era.
Numerical linear algebra in the streaming model
Kenneth L. Clarkson and David P. Woodruff · 2009
Cited alongside, same era.
Raghu Meka · 2010
Closest in time.
Pseudorandom generators for polynomial threshold functions
Raghu Meka and David Zuckerman · 2010
Closest in time.
A variant of the Johnson-Lindenstrauss lemma for circulant matrices
Jan Vybíral · 2010
Closest in time.
Almost optimal unrestricted fast Johnson-Lindenstrauss transform
Nir Ailon and Edo Liberty · 2011
Closest in time.
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with low error
T. S. Jayram and David P. Woodruff · 2011
Closest in time.