Rademacher Chaos, Random Eulerian Graphs and The Sparse Johnson-Lindenstrauss Transform

Etude des coefficients de fourier des fonctions de lp(g.)

A Bonami · 1970

Earlier work this paper cites.

A bound on tail probabilities for quadratic forms in independent random variables

D. L. Hanson and F. T. 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

P. Frankl and H. Maehara · 1987

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.

Tail and moment estimates for some types of chaos

Rafał Latała · 1999

Earlier work this paper cites.

Database-friendly random projections: Johnson-lindenstrauss with binary coins

Dimitris Achlioptas · 2003

Cited alongside, same era.

Problems and results in extremal combinatorics–i

Noga Alon · 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.

Rademacher chaos: tail estimates versus limit theorems

Ron Blei and Svante Janson · 2004

Cited alongside, same era.

Approximate nearest neighbors and the fast johnson-lindenstrauss transform

Nir Ailon and Bernard Chazelle · 2006

Cited alongside, same era.

Fast dimension reduction using rademacher series on dual bch codes

Nir Ailon and Edo Liberty · 2008

Cited alongside, same era.

Dense fast random projections and lean walsh transforms

Edo Liberty, Nir Ailon, and Amit Singer · 2008

Later among the works it cites.

On variants of the johnson–lindenstrauss lemma

Original

Jiří Matoušek · 2008

Later among the works it cites.

A sparse johnson lindenstrauss transform

Anirban Dasgupta, Ravi Kumar, and Tamás Sarlos · 2010

Closest in time.

A derandomized sparse johnson-lindenstrauss transform

Original

Daniel M. Kane and Jelani Nelson · 2010

Closest in time.

An almost optimal unrestricted fast johnson-lindenstrauss transform

Nir Ailon and Edo Liberty · 2011

Closest in time.