Fetching the paper…
Reading the bibliography…
For any integers $d, n \geq 2$ and $1/({\min\{n,d\}})^{0.4999} < \varepsilon<1$, we show the existence of a set of $n$ vectors $X\subset \mathbb{R}^d$ such that any embedding $f:X\rightarrow \mathbb{R}^m$ satisfying $$ \forall x,y\in X,\ (1-\varepsilon)\|x-y\|_2^2\le \|f(x)-f(y)\|_2^2 \le (1+\varepsilon)\|x-y\|_2^2 $$ must have $$ m = \Omega(\varepsilon^{-2} \lg n).
Lower bounds on the maximum cross correlation of signals
Lloyd R. Welch · 1974
Earlier work this paper cites.
Bounds for packings of metric spaces and some of their applications (in Russian)
Vladimir I. Levenshtein · 1983
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 volume of convex bodies and Banach space geometry
Gilles Pisier · 1989
Earlier work this paper cites.
Simple construction of almost k-wise independent random variables
Noga Alon, Oded Goldreich, Johan Håstad, and René Peralta · 1992
Earlier work this paper cites.
Minkowski Geometry
Anthony C. Thompson · 1996
Earlier work this paper cites.
Efficient search for approximate nearest neighbor in high dimensional spaces
Eyal Kushilevitz, Rafail Ostrovsky, and Yuval Rabani · 2000
Earlier work this paper cites.
Problems and results in extremal combinatorics–I
Noga Alon · 2003
Cited alongside, same era.
Data streams: Algorithms and applications
S. Muthukrishnan · 2005
Cited alongside, same era.
Robust uncertainty principles: exact signal reconstruction from highly incomplete frequency information
Emmanuel Candès, Justin Romberg, and Terence Tao · 2006
Cited alongside, same era.
Compressed sensing
David Donoho · 2006
Cited alongside, same era.
Almost optimal explicit Johnson-Lindenstrauss families
Daniel M. Kane, Raghu Meka, and Jelani Nelson · 2011
Cited alongside, same era.
Graph sparsification by effective resistances
Daniel A. Spielman and Nikhil Srivastava · 2011
Cited alongside, same era.
Optimal bounds for Johnson-Lindenstrauss transforms and streaming problems with subconstant error
T. S. Jayram and David P. Woodruff · 2013
Later among the works it cites.
On deterministic sketching and streaming for sparse recovery and norm estimation
Jelani Nelson, Huy L. Nguy e ^ ~ \tilde{\hat{\mbox{e}}} n, and David P. Woodruff · 2014
Later among the works it cites.
Sketching as a tool for numerical linear algebra
David P. Woodruff · 2014
Later among the works it cites.
Randomized dimensionality reduction for k-means clustering
Christos Boutsidis, Anastasios Zouzias, Michael W. Mahoney, and Petros Drineas · 2015
Later among the works it cites.
Dimensionality reduction for k-means clustering and low rank approximation
Michael B. Cohen, Sam Elder, Cameron Musco, Christopher Musco, and Mădălina Persu · 2015
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
Approximate nearest neighbor: Towards removing the curse of dimensionality
Sariel Har-Peled, Piotr Indyk, and Rajeev Motwani · 2012
Cited alongside, same era.
The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
Kasper Green Larsen and Jelani Nelson · 2016
Closest in time.
Optimal compression of approximate inner products and dimension reduction
Noga Alon and Bo’az Klartag · 2017
Closest in time.