Fetching the paper…
Reading the bibliography…
The purpose of this article is to survey some of the context, achievements, challenges and mysteries of the field of metric dimension reduction, including new perspectives on major older results as well as recent advances.
Les dimensions d’un ensemble abstrait
M. Fréchet · 1910
Earlier work this paper cites.
Ensembles impropres et nombre dimensionnel. I, II
G. Bouligand · 1928
Earlier work this paper cites.
Dimensionstheorie
K. Menger · 1928
Earlier work this paper cites.
Une remarque sur l’homéomorphie des champs fonctionels
S. Mazur · 1929
Earlier work this paper cites.
über eine n n -dimensionale Universalmenge im R 2 n + 1 R^{2n+1}
G. Nöbeling · 1931
Earlier work this paper cites.
Théorie des opérations linéaires
S. Banach · 1932
Earlier work this paper cites.
H. Whitney · 1936
Earlier work this paper cites.
Metric spaces and positive definite functions
I. J. Schoenberg · 1938
Earlier work this paper cites.
Extremum problems with inequalities as subsidiary conditions
F. John · 1948
Earlier work this paper cites.
A theorem on triangles in a metric space and some of its applications
A. D. Aleksandrov · 1951
Earlier work this paper cites.
Résumé des résultats essentiels dans la théorie des produits tensoriels topologiques et des espaces nucléaires
A. Grothendieck · 1952
Earlier work this paper cites.
Résumé de la théorie métrique des produits tensoriels topologiques
A. Grothendieck · 1953
Earlier work this paper cites.
Sur certaines classes de suites dans les espaces de Banach et le théorème de Dvoretzky-Rogers
A. Grothendieck · 1953
Earlier work this paper cites.
C 1 C^{1} isometric imbeddings
J. Nash · 1954
Earlier work this paper cites.
Produits tensoriels topologiques et espaces nucléaires
A. Grothendieck · 1955
Earlier work this paper cites.
Some results on convex bodies and Banach spaces
A. Dvoretzky · 1961
Earlier work this paper cites.
A convexity condition in Banach spaces and the strong law of large numbers
A. Beck · 1962
Earlier work this paper cites.
Some matrix-inequalities and metrization of matric-space
J. von Neumann · 1962
Earlier work this paper cites.
Extremal problems in graph theory
P. Erdős · 1964
Earlier work this paper cites.
On the Betti numbers of real varieties
J. Milnor · 1964
Earlier work this paper cites.
Sur l’homologie des variétés algébriques réelles
R. Thom · 1965
Earlier work this paper cites.
Absolutely summing operators in L p L_{p} -spaces and their applications
J. Lindenstrauss and A. Pełczyński · 1968
Earlier work this paper cites.
The ℒ p \mathcal{L}_{p} spaces
J. Lindenstrauss and H. P. Rosenthal · 1969
Earlier work this paper cites.
A lower bound for the smallest eigenvalue of the Laplacian
J. Cheeger · 1970
Earlier work this paper cites.
Uniform structures and square roots in topological groups. I, II
P. Enflo · 1970
Earlier work this paper cites.
Analyse harmonique non-commutative sur certains espaces homogènes
R. R. Coifman and G. Weiss · 1971
Earlier work this paper cites.
Banach spaces which can be given an equivalent uniformly convex norm
P. Enflo · 1972
Earlier work this paper cites.
Super-reflexive Banach spaces
R. C. James · 1972
Earlier work this paper cites.
Caractérisation d’une classe d’espaces de Banach par des propriétés de séries aléatoires vectorielles
B. Maurey and G. Pisier · 1973
Earlier work this paper cites.
It is impossible to imbed ℓ p \ell_{p} or c 0 c_{0} into an arbitrary Banach space
B. S. Cirel’son · 1974
Earlier work this paper cites.
A uniformly convex Banach space which contains no l p l_{p}
T. Figiel and W. B. Johnson · 1974
Earlier work this paper cites.
The moduli of smoothness and convexity and the Rademacher averages of trace classes S p ( 1 ⩽ p < ∞ ) S_{p}(1\leqslant p<\infty)
N. Tomczak-Jaegermann · 1974
Earlier work this paper cites.
Martingales with values in uniformly convex spaces
G. Pisier · 1975
Earlier work this paper cites.
Séries de variables aléatoires vectorielles indépendantes et propriétés géométriques des espaces de Banach
B. Maurey and G. Pisier · 1976
Earlier work this paper cites.
Banach spaces of analytic functions and absolutely summing operators
A. Peł czyński · 1976
Earlier work this paper cites.
On uniformly homeomorphic normed spaces
M. Ribe · 1976
Earlier work this paper cites.
Extremal graph theory
B. Bollobás · 1978
Earlier work this paper cites.
On infinite-dimensional topological groups
P. Enflo · 1978
Earlier work this paper cites.
Un théorème sur les opérateurs linéaires entre espaces de Banach qui se factorisent par un espace de Hilbert
G. Pisier · 1980
Earlier work this paper cites.
The efficient generation of random orthogonal matrices with an application to condition estimators
G. W. Stewart · 1980
Earlier work this paper cites.
Hélices et quasi-hélices
J.-P. Kahane · 1981
Earlier work this paper cites.
Remarques sur un résultat non publié de B. Maurey
G. Pisier · 1981
Earlier work this paper cites.
Applications of ultrapowers to the uniform and Lipschitz classification of Banach spaces
S. Heinrich and P. Mankiewicz · 1982
Earlier work this paper cites.
Limit theorems for uniform distributions on spheres in high-dimensional Euclidean spaces
A. J. Stam · 1982
Earlier work this paper cites.
Plongements lipschitziens dans 𝐑 n {\bf R}^{n}
P. Assouad · 1983
Earlier work this paper cites.
Counterexamples to a conjecture of Grothendieck
G. Pisier · 1983
Earlier work this paper cites.
New Banach space properties of the disc algebra and H ∞ H^{\infty}
J. Bourgain · 1984
Earlier work this paper cites.
Extensions of Lipschitz mappings into a Hilbert space
W. B. Johnson and J. Lindenstrauss · 1984
Earlier work this paper cites.
Characterizations of almost surely continuous p p -stable random Fourier series and strongly stationary processes
M. B. Marcus and G. Pisier · 1984
Earlier work this paper cites.
Explicit concentrators from generalized N N -gons
R. M. Tanner · 1984
Earlier work this paper cites.
λ 1 , \uplambda_{1}, isoperimetric inequalities for graphs, and superconcentrators
N. Alon and V. D. Milman · 1985
Earlier work this paper cites.
On Lipschitz embedding of finite metric spaces in Hilbert space
J. Bourgain · 1985
Earlier work this paper cites.
Subspaces of l N ∞ l^{\infty}_{N} , arithmetical diameter and Sidon sets
J. Bourgain · 1985
Earlier work this paper cites.
Dichotomie du cotype pour les espaces invariants
J. Bourgain and V. Milman · 1985
Earlier work this paper cites.
The number of polytopes, configurations and real matroids
N. Alon · 1986
Earlier work this paper cites.
The metrical interpretation of superreflexivity in Banach spaces
J. Bourgain · 1986
Earlier work this paper cites.
On Hilbertian subsets of finite metric spaces
J. Bourgain, T. Figiel, and V. Milman · 1986
Earlier work this paper cites.
On type of metric spaces
J. Bourgain, V. Milman, and H. Wolfson · 1986
Earlier work this paper cites.
Asymptotic theory of finite-dimensional normed spaces
V. D. Milman and G. Schechtman · 1986
Earlier work this paper cites.
Probabilistic methods in the geometry of Banach spaces
G. Pisier · 1986
Earlier work this paper cites.
Remarks on the extension of Lipschitz maps defined on discrete sets and uniform homeomorphisms
J. Bourgain · 1987
Earlier work this paper cites.
On Lipschitz embedding of finite metric spaces in low-dimensional normed spaces
W. B. Johnson, J. Lindenstrauss, and G. Schechtman · 1987
Earlier work this paper cites.
More on embedding subspaces of L p L_{p} in l r n l^{n}_{r}
G. Schechtman · 1987
Earlier work this paper cites.
The Johnson-Lindenstrauss lemma and the sphericity of some graphs
P. Frankl and H. Maehara · 1988
Earlier work this paper cites.
On Milman’s inequality and random subspaces which escape through a mesh in 𝐑 n {\bf R}^{n}
Y. Gordon · 1988
Earlier work this paper cites.
Approximation of zonoids by zonotopes
J. Bourgain, J. Lindenstrauss, and V. Milman · 1989
Earlier work this paper cites.
Métriques de Carnot-Carathéodory et quasiisométries des espaces symétriques de rang un
P. Pansu · 1989
Earlier work this paper cites.
Approximate counting, uniform generation and rapidly mixing Markov chains
A. Sinclair and M. Jerrum · 1989
Earlier work this paper cites.
Embedding subspaces of L 1 L_{1} into l 1 N l^{N}_{1}
M. Talagrand · 1990
Earlier work this paper cites.
Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces
J. Arias-de Reyna and L. Rodríguez-Piazza · 1992
Earlier work this paper cites.
Markov chains, Riesz transforms and Lipschitz maps
K. Ball · 1992
Earlier work this paper cites.
A. D. Aleksandrov spaces with curvatures bounded below
Y. Burago, M. Gromov, and G. Perelman · 1992
Earlier work this paper cites.
Note on bi-Lipschitz embeddings into normed spaces
J. Matoušek · 1992
Earlier work this paper cites.
Ramsey-like properties for bi-Lipschitz mappings of finite metric spaces
J. Matoušek · 1992
Earlier work this paper cites.
Factorization of operator valued analytic functions
G. Pisier · 1992
Earlier work this paper cites.
Approximating a helix in finitely many dimensions
M. Talagrand · 1992
Earlier work this paper cites.
Asymptotic invariants of infinite groups
M. Gromov · 1993
Earlier work this paper cites.
An upper bound on the diameter of a graph from eigenvalues associated with its Laplacian
F. R. K. Chung, V. Faber, and T. A. Manteuffel · 1994
Earlier work this paper cites.
On the best constant for the Besicovitch covering theorem
Z. Füredi and P. A. Loeb · 1994
Earlier work this paper cites.
A new series of dense graphs of high girth
F. Lazebnik, V. A. Ustimenko, and A. J. Woldar · 1995
Earlier work this paper cites.
The geometry of graphs and some of its algorithmic applications
N. Linial, E. London, and Y. Rabinovich · 1995
Earlier work this paper cites.
An “isomorphic” version of Dvoretzky’s theorem
V. D. Milman and G. Schechtman · 1995
Earlier work this paper cites.
Embedding subspaces of L p L_{p} in l p N l^{N}_{p}
M. Talagrand · 1995
Earlier work this paper cites.
On the distortion required for embedding finite metric spaces into normed spaces
J. Matoušek · 1996
Earlier work this paper cites.
On the nonexistence of bi-Lipschitz parameterizations and geometric problems about A ∞ A_{\infty} -weights
S. Semmes · 1996
Cited alongside, same era.
Fractured fractals and broken dreams
G. David and S. Semmes · 1997
Cited alongside, same era.
On embedding expanders into ℓ p \ell_{p} spaces
J. Matoušek · 1997
Cited alongside, same era.
Concentration of the distance in finite-dimensional normed spaces
J. Arias-de Reyna, K. Ball, and R. Villa · 1998
Cited alongside, same era.
An algorithmic theory of learning: robust concepts and random projection
R. I. Arriaga and S. Vempala · 1999
Cited alongside, same era.
Poincaré inequalities and quasiconformal structure on the boundary of some hyperbolic buildings
M. Bourdon and H. Pajot · 1999
Cited alongside, same era.
Dimension reduction: A guided tour
C. J. C. Burges · 2010
Later among the works it cites.
Ultra-low-dimensional embeddings for doubling metrics
T.-H. H. Chan, A. Gupta, and K. Talwar · 2010
Later among the works it cites.
Differentiating maps into L 1 L^{1} , and the geometry of BV functions
J. Cheeger and B. Kleiner · 2010
Later among the works it cites.
Probability: theory and examples
R. Durrett · 2010
Later among the works it cites.
Improved bounds in the scaled Enflo type inequality for Banach spaces
O. Giladi and A. Naor · 2010
Later among the works it cites.
The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite
W. B. Johnson and A. Naor · 2010
Later among the works it cites.
alphaXiv searches the wider corpus for related work and actual follow-ups.
alphaXiv is searching for related work…
On equilateral simplices in normed spaces
P. Braß · 1999
Cited alongside, same era.
Differentiability of Lipschitz functions on metric measure spaces
J. Cheeger · 1999
Cited alongside, same era.
Approximate nearest neighbors: towards removing the curse of dimensionality
P. Indyk and R. Motwani · 1999
Cited alongside, same era.
Bilipschitz embeddings of metric spaces into Euclidean spaces
S. Semmes · 1999
Cited alongside, same era.
The free quasiworld. Freely quasiconformal and related maps in Banach spaces
J. Väisälä · 1999
Cited alongside, same era.
Geometric nonlinear functional analysis. Vol. 1
Y. Benyamini and J. Lindenstrauss · 2000
Cited alongside, same era.
Advances in metric embedding theory
I. Abraham, Y. Bartal, and O. Neiman · 2011
Later among the works it cites.
Near linear lower bound for dimension reduction in ℓ 1 \ell_{1}
A. Andoni, M. S. Charikar, O. Neiman, and H. L. Nguyen · 2011
Later among the works it cites.
Dimensionality reduction: beyond the Johnson-Lindenstrauss bound
Y. Bartal, B. Recht, and L. J. Schulman · 2011
Later among the works it cites.
Compression bounds for Lipschitz maps from the Heisenberg group to L 1 L_{1}
J. Cheeger, B. Kleiner, and A. Naor · 2011
Later among the works it cites.
Improved bounds in the metric cotype inequality for Banach spaces
O. Giladi, M. Mendel, and A. Naor · 2011
Later among the works it cites.
Making doubling metrics geodesic
A. Gupta and K. Talwar · 2011
Later among the works it cites.
Geometric approximation algorithms
S. Har-Peled · 2011
Later among the works it cites.
New and improved Johnson-Lindenstrauss embeddings via the restricted isometry property
F. Krahmer and R. Ward · 2011
Later among the works it cites.
A note on dichotomies for metric transforms
M. Mendel and A. Naor · 2011
Later among the works it cites.
Poincaré inequalities, embeddings, and wild groups
A. Naor and L. Silberman · 2011
Later among the works it cites.
On metric characterizations of some classes of Banach spaces
M. I. Ostrovskii · 2011
Later among the works it cites.
The Ribe programme
K. Ball · 2012
Later among the works it cites.
Twice-Ramanujan sparsifiers
J. Batson, D. A. Spielman, and N. Srivastava · 2012
Later among the works it cites.
A spectral gap theorem in SU ( d ) {\rm SU}(d)
J. Bourgain and A. Gamburd · 2012
Later among the works it cites.
Locally decodable codes and the failure of cotype for projective tensor products
J. Briët, A. Naor, and O. Regev · 2012
Later among the works it cites.
Bourgain’s discretization theorem
O. Giladi, A. Naor, and G. Schechtman · 2012
Later among the works it cites.
Grothendieck-type inequalities in combinatorial optimization
S. Khot and A. Naor · 2012
Later among the works it cites.
An application of metric cotype to quasisymmetric embeddings
A. Naor · 2012
Later among the works it cites.
An introduction to the Ribe program
A. Naor · 2012
Later among the works it cites.
Assouad’s theorem with dimension independent of the snowflaking
A. Naor and O. Neiman · 2012
Later among the works it cites.
Large scale geometry
P. W. Nowak and G. Yu · 2012
Later among the works it cites.
Grothendieck’s theorem, past and present
G. Pisier · 2012
Later among the works it cites.
An almost optimal unrestricted fast Johnson-Lindenstrauss transform
N. Ailon and E. Liberty · 2013
Later among the works it cites.
Sharp quantitative nonembeddability of the Heisenberg group into superreflexive Banach spaces
T. Austin, A. Naor, and R. Tessera · 2013
Later among the works it cites.
A non-probabilistic proof of the Assouad embedding theorem with bounds on the dimension
G. David and M. Snipes · 2013
Later among the works it cites.
Dimension reduction for finite trees in ℓ 1 \ell_{1}
J. R. Lee, A. de Mesmay, and M. Moharrami · 2013
Later among the works it cites.
Markov convexity and local rigidity of distorted metrics
M. Mendel and A. Naor · 2013
Later among the works it cites.
On multiplicative λ \uplambda -approximations and some geometric applications
I. Newman and Y. Rabinovich · 2013
Later among the works it cites.
Metric embeddings
M. I. Ostrovskii · 2013
Later among the works it cites.
Entropy-based bounds on dimension reduction in L 1 L^{1}
O. Regev · 2013
Later among the works it cites.
Approximate distance oracles with constant query time
S. Chechik · 2014
Later among the works it cites.
Randomized large distortion dimension reduction
A. Dmitriyuk and Y. Gordon · 2014
Later among the works it cites.
Sparser Johnson-Lindenstrauss transforms
D. M. Kane and J. Nelson · 2014
Later among the works it cites.
A doubling subset of L p L_{p} for p > 2 p>2 that is inherently infinite dimensional
V. Lafforgue and A. Naor · 2014
Later among the works it cites.
Vertical versus horizontal Poincaré inequalities on the Heisenberg group
V. Lafforgue and A. Naor · 2014
Later among the works it cites.
Nonlinear spectral calculus and super-expanders
M. Mendel and A. Naor · 2014
Later among the works it cites.
Comparison of metric spectral gaps
A. Naor · 2014
Later among the works it cites.
Convex bodies: the Brunn-Minkowski theory
R. Schneider · 2014
Later among the works it cites.
Upper and lower bounds for stochastic processes
M. Talagrand · 2014
Later among the works it cites.
Snowflake universality of Wasserstein spaces
A. Andoni, A. Naor, and O. Neiman · 2015
Later among the works it cites.
On the impossibility of dimension reduction for doubling subsets of ℓ p \ell_{p}
Y. Bartal, L.-A. Gottlieb, and O. Neiman · 2015
Later among the works it cites.
Toward a unified theory of sparse dimensionality reduction in Euclidean space
J. Bourgain, S. Dirksen, and J. Nelson · 2015
Later among the works it cites.
A nonlinear approach to dimension reduction
L.-A. Gottlieb and R. Krauthgamer · 2015
Later among the works it cites.
Almost optimal pseudorandom generators for spherical caps [extended abstract]
P. K. Kothari and R. Meka · 2015
Later among the works it cites.
Expanders with respect to Hadamard spaces and random graphs
M. Mendel and A. Naor · 2015
Later among the works it cites.
Hölder estimates for the noncommutative Mazur maps
E. Ricard · 2015
Later among the works it cites.
Impossibility of sketching of the 3D transportation metric with quadratic cost
A. Andoni, A. Naor, and O. Neiman · 2016
Later among the works it cites.
Dimension reduction techniques for ℓ p \ell_{p} ( 1 ⩽ p ⩽ 2 1\leqslant p\leqslant 2 ), with applications
Y. Bartal and L.-A. Gottlieb · 2016
Later among the works it cites.
Local random quantum circuits are approximate polynomial-designs
F. G. S. L. Brandão, A. W. Harrow, and M. Horodecki · 2016
Later among the works it cites.
Dimensionality reduction with subgaussian matrices: a unified theory
S. Dirksen · 2016
Later among the works it cites.
Heat flow and quantitative differentiation
T. Hytönen and A. Naor · 2016
Later among the works it cites.
The Johnson-Lindenstrauss lemma is optimal for linear dimensionality reduction
K. G. Larsen and J. Nelson · 2016
Later among the works it cites.
Discrete Riesz transforms and sharp metric X p X_{p} inequalities
A. Naor · 2016
Later among the works it cites.
Low dimensional embeddings of doubling metrics
O. Neiman · 2016
Later among the works it cites.
Chaining introduction with some computer science applications
J. Nelson · 2016
Later among the works it cites.
Metric spaces admitting low-distortion embeddings into all n n -dimensional Banach spaces
M. Ostrovskii and B. Randrianantoanina · 2016
Later among the works it cites.
Optimal compression of approximate inner products and dimension reduction
N. Alon and B. Klartag · 2017
Later among the works it cites.
On isomorphic dimension reduction in ℓ 1 \ell_{1}
A. Andoni, A. Naor, and O. Neiman · 2017
Later among the works it cites.
Approximate near neighbors for general symmetric norms
A. Andoni, H. L. Nguyen, A. Nikolov, I. Razenshteyn, and E. Waingarten · 2017
Later among the works it cites.
On the bi-Lipschitz structure of Wasserstein spaces
T. Austin and A. Naor · 2017
Later among the works it cites.
Diamond convexity: A bifurcation in the Ribe program
A. Eskenazis, M. Mendel, and A. Naor · 2017
Later among the works it cites.
Nonpositive curvature is not coarsely universal
A. Eskenazis, M. Mendel, and A. Naor · 2017
Later among the works it cites.
De Grothendieck à Naor: une promenade dans l’analyse métrique des espaces de Banach
G. Godefroy · 2017
Later among the works it cites.
Optimality of the Johnson–Lindenstrauss lemma
K. G. Larsen and J. Nelson · 2017
Later among the works it cites.
Markov chains and mixing times
D. A. Levin, Y. Peres, and E. L. Wilmer · 2017
Later among the works it cites.
A spectral gap precludes low-dimensional embeddings
A. Naor · 2017
Later among the works it cites.
On Lipschitz extension from finite subsets
A. Naor and Y. Rabani · 2017
Later among the works it cites.
The integrality gap of the Goemans-Linial SDP relaxation for sparsest cut is at least a constant multiple of log n \sqrt{\log n}
A. Naor and R. Young · 2017
Later among the works it cites.
Recipes for stable linear embeddings from Hilbert spaces to ℝ m \mathbb{R}^{m}
G. Puy, M. E. Davies, and R. Gribonval · 2017
Later among the works it cites.
Asymptotic geometric analysis, Part I [book review of MR3331351]
G. Schechtman · 2017
Later among the works it cites.
Data-dependent hashing via nonlinear spectral gaps
A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten · 2018
Closest in time.
Hölder homeomorphisms and approximate nearest neighbors
A. Andoni, A. Naor, A. Nikolov, I. Razenshteyn, and E. Waingarten · 2018
Closest in time.
Impossibility of dimension reduction in the nuclear norm
A. Naor, G. Pisier, and G. Schechtman · 2018
Closest in time.
Foliated corona decompositions
A. Naor and R. Young · 2018
Closest in time.
Vertical perimeter versus horizontal perimeter
A. Naor and R. Young · 2018
Closest in time.
Polylog dimensional subspaces of ℓ ∞ N \ell_{\infty}^{N}
G. Schechtman and N. Tomczak-Jaegermann · 2018
Closest in time.
Random series of trace class operators
G. Pisier · 2090
Closest in time.