{"id":"arxiv/2610.41945","url":"https://arxiv.org/abs/2610.41945","tags":["cs.DS","cs.CG","math.MG"],"score":0,"title":"Optimal Average Distortion for Non-Expansive Embeddings of Euclidean Metrics into the Line: With applications to cut-matching games and vertex expansion","domain":"cs.DS","source":"arxiv","authors":["Jack Spalding-Jamieson"],"reviews":0,"subject":"cs.DS","summary":"We show that any $n$-point Euclidean metric admits a non-expansive embedding into the line with average distortion at most $O\\left(\\sqrt{\\frac{\\log n}{\\log\\log n}}\\right)$, 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.","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-10-30","reactions":{}}