Nonembeddability theorems via Fourier analysis

DOI10.1007/s00208-005-0745-0zbMath1102.46051arXivmath/0510547OpenAlexW2038921147WikidataQ125386455 ScholiaQ125386455MaRDI QIDQ2491108

Assaf Naor, Subhash A. Khot

Publication date: 26 May 2006

Published in: Mathematische Annalen (Search for Journal in Brave)

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

zbMATH Keywords

Fourier analysismetric spacedistortiondiscrete cubebi-Lipschitz mappingnonembeddability, embeddings of metric spaces

Mathematics Subject Classification ID

Topological spaces with richer structures (54E99) Isomorphic theory (including renorming) of Banach spaces (46B03) Approximation algorithms (68W25) Continuous and differentiable maps in nonlinear functional analysis (46T20)

Related Items

Sketching and Embedding are Equivalent for Norms, Approximating tree edit distance through string edit distance, Coarse differentiation and multi-flows in planar graphs, Vertical perimeter versus horizontal perimeter, Gaussian noise sensitivity and Fourier tails, Stochastic approximation of lamplighter metrics, 𝐿₁-distortion of Wasserstein metrics: A tale of two dimensions, Least distortion Euclidean embeddings of flat tori, An introduction to the Ribe program, The Brin Prize works of Tim Austin, Talagrand's influence inequality revisited, Wasserstein distance and metric trees, Quantum Talagrand, KKL and Friedgut's theorems and the learnability of quantum Boolean functions, Lipschitz-free Spaces on Finite Metric Spaces, Discrete logarithmic Sobolev inequalities in Banach spaces, Amenable groups with very poor compression into Lebesgue spaces, On relations between transportation cost spaces and \(\ell_1\), Strong contraction and influences in tail spaces, Unnamed Item, Unnamed Item, Towards a proof of the Fourier-entropy conjecture?, Comparison of Metric Spectral Gaps, Quantitative bi-Lipschitz embeddings of bounded-curvature manifolds and orbifolds, Nonlinear spectral calculus and super-expanders, On the Fourier tails of bounded functions over the discrete cube, The Euclidean distortion of the lamplighter group., Polylogarithmic Approximation for Edit Distance and the Asymmetric Query Complexity, Snowflake universality of Wasserstein spaces, An average John theorem, The Andoni–Krauthgamer–Razenshteyn Characterization of Sketchable Norms Fails for Sketchable Metrics, Expanders with respect to Hadamard spaces and random graphs, Properties of the \(d\)-dimensional Earth mover's problem, Nonpositive curvature is not coarsely universal, Isometric structure of transportation cost spaces on finite metric spaces, The Unique Games Conjecture, Integrality Gap for Cut Problems and Embeddability of Negative-Type Metrics into ℓ ₁, The Restricted Isometry Property of Subsampled Fourier Matrices

Uses Software

• EMD

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Korkin-Zolotarev bases and successive minima of a lattice and its reciprocal lattice
• Asymptotic theory of finite dimensional normed spaces. With an appendix by M. Gromov: Isoperimetric inequalities in Riemannian manifolds
• The metrical interpretation of superreflexivity in Banach spaces
• On Lipschitz embedding of finite metric spaces in Hilbert space
• Inequalities in Fourier analysis
• Martingales with values in uniformly convex spaces
• Sharp uniform convexity and smoothness inequalities for trace norms
• Influences of variables and threshold intervals under group symmetries
• On embedding expanders into \(\ell_p\) spaces
• Euclidean quotients of finite metric spaces
• On the distribution of the Fourier spectrum of Boolean functions
• The earth mover's distance as a metric for image retrieval
• The geometry of graphs and some of its algorithmic applications
• Affine approximation of Lipschitz functions and nonlinear quotients
• On metric Ramsey-type phenomena
• Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces
• Étude des coefficients de Fourier des fonctions de \(L^ p(G)\)
• On the nonexistence of uniform homeomorphisms between \(L^ p\)-spaces
• Quasisymmetric embeddings, the observable diameter, and expansion properties of graphs
• \(C^1\) isometric imbeddings
• From deep holes to free planes
• Approximate nearest neighbors and sequence comparison with block operations
• Similarity estimation techniques from rounding algorithms
• A new family of Cayley expanders (?)
• A sublinear algorithm for weakly approximating edit distance
• A note on the isoperimetric constant
• Algorithms on Strings, Trees and Sequences
• An O(log k) Approximate Min-Cut Max-Flow Theorem and Approximation Algorithm
• Symmetric groups and expanders
• On Type of Metric Spaces
• Remarks on non linear type and Pisiers inequality
• Low distortion embeddings for edit distance
• Metric structures for Riemannian and non-Riemannian spaces. Transl. from the French by Sean Michael Bates. With appendices by M. Katz, P. Pansu, and S. Semmes. Edited by J. LaFontaine and P. Pansu
• Geometry of cuts and metrics
• Metric cotype