
Summary: A major open problem in the field of metric embedding is the existence of dimension reduction for \(n\)-point subsets of Euclidean space, such that both distortion and dimension depend only on the doubling constant of the point set, and not on its cardinality. In this paper, we negate this possibility for \(\ell_p\) spaces with \(p>2\). In particular, we introduce an \(n\)-point subset of \(\ell_p\) with doubling constant \(O(1)\), and demonstrate that any embedding of the set into \(\ell_p^d\) with distortion \(D\) must have \(D\geq\Omega((\frac{\log n}{d})^{\frac{1}{2}-\frac{1}{p}})\).
Distance in graphs, doubling dimension, Computer graphics; computational geometry (digital and algorithmic aspects), Applications of graph theory, Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science, embeddings, Laakso graph
Distance in graphs, doubling dimension, Computer graphics; computational geometry (digital and algorithmic aspects), Applications of graph theory, Embeddings of discrete metric spaces into Banach spaces; applications in topology and computer science, embeddings, Laakso graph
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Average | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
