Measured descent: A new embedding method for finite metrics
From MaRDI portal
Publication:2571745
DOI10.1007/s00039-005-0527-6zbMath1108.46010arXivcs/0412008OpenAlexW3098011928MaRDI QIDQ2571745
Assaf Naor, Robert Krauthgamer, James R. Lee, Manor Mendel
Publication date: 14 November 2005
Published in: Geometric and Functional Analysis. GAFA (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/cs/0412008
embeddingdistortion\(n\)-point metric spacedecomposition bundlemeasured descentpadded decompositionvolume-respecting
Graph theory (including graph drawing) in computer science (68R10) Local theory of Banach spaces (46B07) Probabilistic methods in Banach space theory (46B09) Embedding (54C25)
Related Items
Diffusive estimates for random walks on stationary random graphs of polynomial growth, A note on multiflows and treewidth, \(\ell ^2_2\) spreading metrics for vertex ordering problems, Vertical perimeter versus horizontal perimeter, Approximating the bandwidth of caterpillars, Metric Embedding via Shortest Path Decompositions, Markov type and threshold embeddings, Negative-type diversities, a multi-dimensional analogue of negative-type metrics, Terminal embeddings, Metric decompositions of path-separable graphs, Hardness results for approximating the bandwidth, Reliable Spanners for Metric Spaces, Labelings vs. embeddings: on distributed and prioritized representations of distances, Relations between scaling exponents in unimodular random graphs, Compression bounds for Lipschitz maps from the Heisenberg group to \(L_{1}\), Maximum gradient embeddings and monotone clustering, Designing universal causal deep learning models: The geometric (Hyper)transformer, Interactions of computational complexity theory and mathematics, On the optimality of gluing over scales, Euclidean distortion and the sparsest cut, Distance estimation and object location via rings of neighbors, Volume in general metric spaces, Metric uniformization and spectral bounds for graphs, Advances in metric embedding theory, Combinatorial theorems about embedding trees on the real line, On the Structure of Isometrically Embeddable Metric Spaces, Labeling schemes for weighted dynamic trees, Fréchet embeddings of negative type metrics, Diffusion wavelets, Markov chains in smooth Banach spaces and Gromov-hyperbolic metric spaces, Unnamed Item, Ramsey partitions and proximity data structures, A tight bound on approximating arbitrary metrics by tree metrics, Fractal dimension and lower bounds for geometric problems, Quasimetric embeddings and their applications, Unnamed Item, A node-capacitated Okamura-Seymour theorem, Volume distortion for subsets of Euclidean spaces, On the Impossibility of Dimension Reduction for Doubling Subsets of $\ell_{p}$, Light spanners for high dimensional norms via stochastic decompositions, Low dimensional embeddings of doubling metrics
