Skip to content
DraconiticResearch
Search Sources API
181,713 studies31 sourcesUpdated 20 min ago
PreprintarXiv licencearXiv

Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion

  • Jack Spalding-Jamieson
Open at sourcePDFDOICite

Abstract

We show that any n-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most O(√((log n)/(loglog n))), matching a known lower bound. We also present two applications of this result. First, we give a cut-player strategy with an optimal spectral guarantee for the undirected cut-matching game. Second, we give an improved spectral approximation for vertex expansion in high-degree graphs.

Related

  1. Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance
    Fengqi Hou
    arXivPreprintarXiv licenceFull textGeneral mathematicsarXiv
  2. A threshold phenomenon for embeddings of Euclidean snowflakes and impossibility of dimension reduction
    Assaf Naor, Kevin Ren
    arXivPreprintCC BY 4.0Full textGeometry & topologyarXiv
  3. Quasiconformal distortion of the lower dimension and applications
    Efstathios Konstantinos Chrontsios Garitsis, Jeremy T. Tyson
    arXivPreprintarXiv licenceFull textAnalysis & PDEsGeometry & topologyarXiv
  4. A Self-Coupling Gaussian Extremal Inequality for Information-Constrained Optimal Transport with Applications to Rate-Distortion-Perception
    Jiayang Zou, Jun Chen, Ayfer Özgür +1
    arXivPreprintCC0Full textGeneral mathematicsarXiv
  5. Computation and Applications of Euclidean and Normed Representations of Massive Data
    Max Ovsiankin
    arXivPreprintarXiv licenceFull textOptimisation & controlarXiv

Cite

BibTeXRIS
BibTeX
@misc{spaldingjamieson2026optimal,
  title = {{Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion}},
  author = {Jack Spalding-Jamieson},
  howpublished = {arXiv},
  year = {2026},
  month = oct,
  doi = {10.48550/arxiv.2610.41945},
  eprint = {2610.41945},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2610.41945},
}
RIS
TY  - UNPB
TI  - Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion
AU  - Jack Spalding-Jamieson
PY  - 2026
DA  - 2026/10/30
PB  - arXiv
DO  - 10.48550/arxiv.2610.41945
UR  - https://arxiv.org/abs/2610.41945
AB  - We show that any n-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most O(√((log n)/(loglog n))), matching a known lower bound. We also present two applications of this result. First, we give a cut-player strategy with an optimal spectral guarantee for the undirected cut-matching game. Second, we give an improved spectral approximation for vertex expansion in high-degree graphs.
ER  -