Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)

DOI10.1007/S00039-004-0473-8zbMath1069.46005arXivmath/0407520OpenAlexW2962980142MaRDI QIDQ1762655

Assaf Naor, James R. Lee

Publication date: 11 February 2005

Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)

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

zbMATH Keywords

embeddingdistortiondiamond graph

Mathematics Subject Classification ID

Local theory of Banach spaces (46B07) Isomorphic theory (including renorming) of Banach spaces (46B03) Graph theory (05C99)

Related Items (26)

Nonexistence of embeddings with uniformly bounded distortions of Laakso graphs into diamond graphs ⋮ The Johnson-Lindenstrauss lemma almost characterizes Hilbert space, but not quite ⋮ Metric Embedding via Shortest Path Decompositions ⋮ On the geometry of the countably branching diamond graphs ⋮ Entropy-based bounds on dimension reduction in \(L^1\) ⋮ Dimension reduction for finite trees in \(\ell_1\) ⋮ Distortion of embeddings of binary trees into diamond graphs ⋮ \( \varepsilon \)-isometric dimension reduction for incompressible subsets of \(\ell_p\) ⋮ Matrix deviation inequality for ℓp-norm ⋮ Maximum gradient embeddings and monotone clustering ⋮ Expander graphs and their applications ⋮ Bounds on Dimension Reduction in the Nuclear Norm ⋮ On the optimality of gluing over scales ⋮ Euclidean distortion and the sparsest cut ⋮ Linear dimension reduction approximately preserving a function of the $1$-norm ⋮ Real-valued embeddings and sketches for fast distance and similarity estimation ⋮ Snowflake universality of Wasserstein spaces ⋮ Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces ⋮ Impossibility of dimension reduction in the nuclear norm ⋮ No dimension reduction for doubling subsets of \(\ell_q\) when \(q>2\) revisited ⋮ Some applications of Ball’s extension theorem ⋮ Nonpositive curvature is not coarsely universal ⋮ On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$ ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Low dimensional embeddings of doubling metrics

This page was built for publication: Embedding the diamond graph in \(L_p\) and dimension reduction in \(L_1\)