An average John theorem

DOI10.2140/GT.2021.25.1631zbMATH Open1481.46016arXiv1905.01280OpenAlexW2942563862MaRDI QIDQ2048458FDOQ2048458

Authors: Assaf Naor 

Publication date: 6 August 2021

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

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).

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

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

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)

Cites Work

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

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
• Title not available (Why is that?)

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)