An average John theorem

DOI10.2140/GT.2021.25.1631MaRDI QIDQ2048458zbMATH OpenOpenAlexFDO

Authors Assaf Naor

Publication date 6 August 2021

Published in Geometry \& Topology (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1905.01280

zbMATH Keywords

dimension reductionexpander graphsRibe programcomplex interpolation spacesMarkov typemetric embeddingsultraproducts of Banach spacesnonlinear spectral gaps

Mathematics Subject Classification ID

Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science (46B85) Geometric embeddings of metric spaces (30L05) Lipschitz and coarse geometry of metric spaces (51F30) Metric embeddings as related to computational problems and algorithms (68R12)

Abstract: We prove that the $frac12$-snowflake of a finite-dimensional normed space $(X,|cdot{|}_X)$ embeds into a Hilbert space with quadratic average distortion ${\displaystyle }$OBig(sqrt{log mathrm{dim}(X)}Big).${\displaystyle }$ We deduce from this (optimal) statement that if an $n$-vertex expander embeds with average distortion $Dgeqslant1$ into $(X,|cdot{|}_X)$, then necessarily $mathrmdim(X)geqslant{n}^{Omega(1/D)}$, which is sharp by the work of Johnson, Lindenstrauss and Schechtman (1987). This improves over the previously best-known bound $mathrmdim(X)gtrsim(logn{)}^2/D^2$ of Linial, London and Rabinovich (1995), strengthens a theorem of Matouv{s}ek (1996) which resolved questions of Johnson and Lindenstrauss (1982), Bourgain (1985) and Arias-de-Reyna and Rodr{'{i}}guez-Piazza (1992), and answers negatively a question that was posed (for algorithmic purposes) by Andoni, Nguyen, Nikolov, Razenshteyn and Waingarten (2016).

Recommendations

• Exposé Bourbaki 1188 : Average distortion embeddings, nonlinear spectral gaps, and a metric John theorem [after Assaf Naor]
• A spectral gap precludes low-dimensional embeddings
• Advances in metric embedding theory
• On embedding expanders into \(\ell_p\) spaces
• Metric structures in \(L_1\): dimension, snowflakes, and average distortion

Cites work

• scientific article; zbMATH DE number 4138748 (Why is no real title available?)
• scientific article; zbMATH DE number 64771 (Why is no real title available?)
• scientific article; zbMATH DE number 3472726 (Why is no real title available?)
• scientific article; zbMATH DE number 3506603 (Why is no real title available?)
• scientific article; zbMATH DE number 3510978 (Why is no real title available?)
• scientific article; zbMATH DE number 3563703 (Why is no real title available?)
• scientific article; zbMATH DE number 3626044 (Why is no real title available?)
• scientific article; zbMATH DE number 3636708 (Why is no real title available?)
• scientific article; zbMATH DE number 1095489 (Why is no real title available?)
• scientific article; zbMATH DE number 1973925 (Why is no real title available?)
• scientific article; zbMATH DE number 3403210 (Why is no real title available?)
• scientific article; zbMATH DE number 3192371 (Why is no real title available?)
• scientific article; zbMATH DE number 3031612 (Why is no real title available?)
• scientific article; zbMATH DE number 3033168 (Why is no real title available?)
• A NOTE ON NON-AMENABILITY OF ℬ(ℓ_p) FOR p=1,2
• A proof that every uniformly convex space is reflexive
• A reinforcement of property (T)
• A spectral gap precludes low-dimensional embeddings
• A strengthened Banach property (T) and the fast Fourier transform
• Advances in metric embedding theory
• Affine approximation of Lipschitz functions and nonlinear quotients
• An introduction to the Ribe program
• Approximate near neighbors for general symmetric norms
• Banach space actions and \(L^2\)-spectral gap
• Banach spaces which can be given an equivalent uniformly convex norm
• Bourbaki seminar. Volume 2011/2012. Exposés 1043--1058
• CAT(0) spaces and expanders.
• Combinatorial harmonic maps and discrete-group actions on Hadamard spaces
• Combinatorics, Paul Erdős is eighty. Vol. 2
• Comparison of metric spectral gaps
• Complex interpolation between Hilbert, Banach and operator spaces
• Data-dependent hashing via nonlinear spectral gaps
• Diameters, distortion, and eigenvalues
• Differentiability of Lipschitzian mappings between Banach spaces
• Discrete Riesz transforms and sharp metric \(X_p\) inequalities
• Embeddability of snowflaked metrics with applications to the nonlinear geometry of the spaces \(L_p\) and \(\ell_p\) for \(0<p<\infty\)
• Euclidean quotients of finite metric spaces
• Every connected regular graph of even degree is a Schreier coset graph
• Expander graphs and their applications
• Expanders with respect to Hadamard spaces and random graphs
• Extending Lipschitz functions via random metric partitions
• Extensions of Lipschitz mappings into a Hilbert space
• Finite metric spaces needing high dimension for Lipschitz embeddings in Banach spaces
• Girth and Euclidean distortion
• Hard metrics from Cayley graphs of abelian groups
• Homéomorphismes Uniformes Entre les Sphères Unité des Espaces D'Interpolation
• Hölder estimates for the noncommutative Mazur maps
• Intermediate spaces and interpolation, the complex method
• Interpolation of Linear Operators
• Interpolation of Uniformly Convex Banach Spaces
• KAZHDAN CONSTANTS FOR SL_n(ℤ)
• Least-distortion Euclidean embeddings of graphs: Products of cycles and expanders
• Lectures on analysis on metric spaces
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• Markov chains, Riesz transforms and Lipschitz maps
• Markov convexity and local rigidity of distorted metrics
• Martingales with values in uniformly convex spaces
• Methods of Geometric Analysis in Extension and Trace Problems
• Metric Spaces and Positive Definite Functions
• Metric \(X_{p}\) inequalities
• Metric cotype
• Metric dimension reduction: a snapshot of the Ribe program
• Metric embeddings. Bilipschitz and coarse embeddings into Banach spaces
• Navigating in the Cayley graphs of \(\text{SL}_N(\mathbb{Z})\) and \(\text{SL}_N(\mathbb{F}_p)\).
• Nonembeddability theorems via Fourier analysis
• Nonlinear spectral calculus and super-expanders
• On Lipschitz embedding of finite metric spaces in Hilbert space
• On Lipschitz extension from finite subsets
• On Lipschitz mappings between Fréchet spaces
• On Type of Metric Spaces
• On average distortion of embedding metrics into the line
• On embedding expanders into \(\ell_p\) spaces
• On the Banach-space-valued Azuma inequality and small-set isoperimetry of Alon-Roichman graphs
• On the Betti Numbers of Real Varieties
• On the complexity of matrix reduction over finite fields
• On the distortion required for embedding finite metric spaces into normed spaces
• On the distribution of distances in homogeneous compact metric spaces
• On the extension of Lipschitz, Lipschitz-Hölder continuous, and monotone functions
• On the moduli of convexity and smoothness
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• On the uniform convexity of L^p and l^p
• On uniform homeomorphisms of the unit spheres of certain Banach lattices
• On uniformly homeomorphic normed spaces
• PLANE WITH $A_{\infty}$ -WEIGHTED METRIC NOT BILIPSCHITZ EMBEDDABLE TO ${\bb R}^n$
• Poincaré inequalities, embeddings, and wild groups.
• Property \((T)\) and rigidity for actions on Banach spaces
• Quantitative nonlinear embeddings into Lebesgue sequence spaces
• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
• Random Cayley graphs and expanders
• Random walk in random groups.
• Sharp uniform convexity and smoothness inequalities for trace norms
• Some applications of the complex interpolation method to Banach lattices
• Spectral calculus and Lipschitz extension for barycentric metric spaces
• Sphere equivalence, Banach expanders, and extrapolation
• Sphere equivalence, property H, and Banach expanders
• Stability of the Lipschitz extension property under metric transforms
• Super-Reflexive Banach Spaces
• The Euclidean distortion of the lamplighter group.
• The distortion problem
• The geometry of graphs and some of its algorithmic applications
• The metrical interpretation of superreflexivity in Banach spaces
• The nonlinear geometry of Banach spaces
• Ultraproducts in Banach space theory.
• Uniform convexity in factor and conjugate spaces
• Uniform nonextendability from nets
• Uniformly Convex Spaces
• \(L^{p}\)-distortion and \(p\)-spectral gap of finite graphs
• Über die zusammenziehende und Lipschitzsche Transformationen

Cited in

(5)

• A spectral gap precludes low-dimensional embeddings
• On quantitative sphere equivalence and extrapolation phenomenon
• The Andoni-Krauthgamer-Razenshteyn characterization of sketchable norms fails for sketchable metrics
• Pythagorean powers of hypercubes
• scientific article; zbMATH DE number 4198367 (Why is no real title available?)

This page was built for publication: An average John theorem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2048458)