CS Paper Radar

On graphically local versions of metric embeddings

Vishesh Jain, Duan Tu

cs.CG math.CO ·submitted 2026-08-16 14:59 UTC · v1
theory

Abstract

We consider the problem of graphically local metric embedding, i.e. embedding points from an arbitrary finite metric space into a target metric space while preserving, up to a small distortion, only a subset of the pairwise distances specified by a bounded degree graph $G$. We provide a general reduction showing that, in many cases, this is no easier than embedding the points while approximately preserving all pairwise distances. As an illustration of our general reduction, we show that there exists a Euclidean metric space $X$ on $n$ points along with a graph $G = (X,E)$ of maximum degree $3$ such that any embedding of $X$ into $\ell_2^m$ which only preserves distances specified by $E$ up to a relative error of $(1+\varepsilon)$ must satisfy $m = Ω(\varepsilon^{-2}\log n)$. Our lower bound matches the upper bound on the dimension coming from the Johnson-Lindenstrauss lemma for approximately preserving all pairwise distances; previously, such a lower bound was known only for the class of noncontracting embeddings [Schechtman-Shraibman, Discrete & Computational Geometry, 2009]. Moreover, the condition that the maximum degree of the graph is $3$ is best possible: for graphs $G$ of maximum degree $2$ (or more generally, treewidth at most $2$), any metric space embeds $G$-isometrically into any two-dimensional normed space.

Closest papers

Nearest neighbours by meaning across the whole index.

The Sharp Dimension Bound in the Johnson--Lindenstrauss Lemma

cs.CG cs.DSmath.MGmath.PR ·2026-08-13 ·Vishesh Jain
theory similarity 0.71
Abstract · 13 pages; comments welcome!

The Johnson--Lindenstrauss lemma asserts that every set of $n$ points in $d$-dimensional Euclidean space embeds into $O(\varepsilon^{-2}\log n)$-dimensional Euclidean space with distortion at most $1+\varepsilon$. Larsen and Nelson conjectured that the optimal target dimension throughout the full range of the parameters $n,d, \varepsilon$ is \[ Θ\left(\min\left\{d,n-1,\frac{\log(2+\varepsilon^2n)}{\varepsilon^2}\right\}\right). \] We resolve this conjecture in the affirmative. In fact, we prove the stronger statement that the upper bound is attained by a linear map. The matching lower bound, due to Larsen--Nelson and Alon--Klartag, holds even for nonlinear embeddings.

0.10

Complete bipartite embeddings, lattice non-embeddability, and non-Euclidean powers of information distance

cs.IT ·2026-09-30 ·Fengqi Hou
similarity 0.69
Abstract · 15 pages. Lean formalization included as ancillary files

We encode the vertices of every finite complete bipartite graph as binary strings at each scale. The information distances between these strings approximate the scaled graph distances with an additive error bounded by a constant independent of the scale. We also assign one fixed infinite binary sequence to each vertex; suitable prefixes satisfy the same distance estimate with logarithmic error. This extends Hutter's construction for $K_{3,3}$ and resolves his open problem on scale-embeddings of finite complete bipartite graphs. Combined with his complete bipartite obstruction, these embeddings show that no positive power of information distance can be represented exactly by distances in a real Hilbert space, resolving his question about such representations. For conditional prefix complexity, we further prove that at most $2^{δ+C}$ strings lie between any two strings with total distance exceeding their mutual distance by at most $δ$, where $C$ is independent of the endpoints. This bound rules out scale-embeddings of the integer line and every positive-dimensional integer lattice, resolving Hutter's lattice embedding problem for both string and sequence embeddings. Restriction to the integer lattice gives the same conclusion for $(\mathbb R^m,\|\cdot\|_1)$ for every $m\ge1$.

0.12

Dimension Thresholds for Relative-Error Representations of Finite Metrics in Pseudo-Euclidean Spaces

cs.CG math.MG ·2026-10-16 ·Nikita Muravya, Aleksandr Bespalov, Anna Vozianova
theory similarity 0.69
Abstract

A finite metric space with $N$ points admits an exact representation in a pseudo-Euclidean space of dimension at most $N-1$. We study the minimum dimension required for relative-error approximation of squared distances. Our main result gives an upper bound for arbitrary metrics in terms of local distance ratios: for $4/5<\varepsilon<1$, dimension $O((N/k)\log N+kρ_k^4\log N/(\varepsilon-4/5)^2)$ suffices, where $ρ_k$ is the largest ratio, over all points, between the distance to the $k$th closest point (counting the point itself) and the nearest-neighbour distance. The proof combines a low-rank landmark approximation with a sparse correction controlled by its factorization norm. For metrics with distances in $[1,Φ]$, where $Φ\ge5$ is fixed, the worst-case dimension is $Θ(N)$ for $0<\varepsilon<4/5$, lies between $Ω(\sqrt N)$ and $O(\sqrt N\log N)$ for $4/5<\varepsilon<12/13$, and is $Θ(\log N)$ for $\varepsilon>(Φ^2-1)/(Φ^2+1)$. For $Φ>5$, an intermediate range remains without matching bounds. Sign-pattern counting yields the $Ω(\sqrt N)$ lower bound for $4/5<\varepsilon<12/13$, while Hadamard matrices give explicit linear lower bounds for $\varepsilon<4/5$ via a known approximate-rank estimate. We also construct configurations with null squared intervals whose minimum representation dimension remains $N-1$ for every $\varepsilon<1$. Finally, for every fixed $0<\varepsilon<3/5$, we show that the quadratic dependence on the parameter $C$ in the dimension bound derived from Deng et al.'s pseudo-Euclidean Johnson-Lindenstrauss lemma is necessary up to a logarithmic factor.

0.22

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

cs.DS cs.CGmath.MG ·2026-10-30 ·Jack Spalding-Jamieson
theory similarity 0.69
Abstract

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.

0.14

Hardness Results for Approximate Distance Labeling in Sparse Graphs

cs.DS ·2026-11-02 ·Tsvi Kopelowitz, Ariel Korin, Liam Roditty
top venuetheory similarity 0.68
Abstract · To appear in SODA 2027

Distance labeling schemes assign short labels to the vertices of a graph so that distances between pairs of vertices can be recovered, exactly or approximately, from the two corresponding labels alone. For sparse graphs, Kosowski, Uznański, and Viennot [PODC'2019] showed that, assuming the hardness of the Sum-Index communication problem, exact distance labeling for sparse unweighted graphs requires near-linear label size. Their construction also gives lower bounds for stretch $1+o(1)$, but does not rule out substantially smaller labels for stretch $1+\varepsilon$, where $\varepsilon>0$ is fixed. We prove lower bounds for this $(1+\varepsilon)$-stretch regime through a density/stretch tradeoff. For every constant integer $k\ge 1$, we show that any approximate distance labeling scheme with stretch strictly smaller than $1+1/k$ for unweighted graphs with $m=O(n^{1+1/k})$ edges requires maximum label size at least $\mathrm{SumIndex}(n)/2^{O_k(\sqrt{\log n})}$ for infinitely many values of $n$. Thus, under the conjecture that $\mathrm{SumIndex}(n)=n^{1-o(1)}$, the maximum label size must be $n^{1-o(1)}$. The main new ingredient is an unweighted graph construction based on $3$-AP-free sets, which replaces the weighted uniqueness mechanism of the previous Sum-Index reduction by an additive uniqueness mechanism and keeps the relevant critical paths short enough to obtain a constant multiplicative distance gap. The same construction also yields near-tight lower bounds for related $2$-hop structures, including hub labeling schemes, shortcut sets, and approximate distance hopsets.

0.38

Fast Approximate $\ell_p$ Chamfer Distance via Lopsided Embeddings and Structured JL

cs.DS cs.LG ·2026-11-08 ·Ying Feng, David P. Woodruff
top venue similarity 0.66
Abstract · Accepted at NeurIPS 2026

For two $d$-dimensional point sets $A, B$ of size $n$, the Chamfer distance from $A$ to $B$ is defined as $\text{CH}(A,B)=\sum_{a \in A} \min_{b \in B} \mathsf{dist}(a, b)$, where $\mathsf{dist}$ is some underlying distance measure. We present efficient algorithms for approximating the Chamfer distance under the $\ell_p$ norm for $1 < p \le 2$. For the general case $1 < p < 2$, we utilize lopsided $\ell_p$ to $\ell_1$ embeddings with weak guarantees. We show that they are sufficient for preserving the Chamfer distance. In the high-dimensional regime, we use Fast Matrix Multiplication techniques to speed up the lopsided embeddings. These lead to $O(nd\cdot \mathrm{poly}(\log \log n, \log(1/\varepsilon))/\varepsilon^2)$ total time. For the specific Euclidean case ($p=2$), we leverage the Fast Johnson-Lindenstrauss Transform based on Toeplitz matrices and re-analyze the previous $\ell_1$-specific Chamfer algorithm in $\ell_2$. These achieve a runtime matching the recent state-of-the-art $\ell_1$ result of $O(nd(\log \log n + \log (1/\varepsilon))/\varepsilon^2)$, improving upon the previous $O(nd \log n/\varepsilon^2)$ bound for $\ell_2$. We also give additional results for the angular distance and upper and lower bounds in the streaming setting.

0.45

Avoiding Distances

cs.CG cs.DMmath.CO ·2026-10-17 ·Adrian Dumitrescu, Zsolt Lángi
similarity 0.66
Abstract · 14 pages, two figures

Given a finite planar point set $X=\{x_1,\ldots,x_n\}$, let $a_1<a_2< \cdots < a_s$ denote the $s \leq {n \choose 2}$ different (Euclidean) distances between points in $X$. The aim is to retain as many of the points as possible such that certain imposed inter-pair distances are avoided. For example, we show that: (A) Given a set $X$ of $n$ points in the plane, an independent set of size $0.2293 n$ in the unit distance graph determined by $X$ can be found in $O(n^2)$ time. For any fixed $k \in \mathbf{N}$ there exists a constant $c_k>0$ such that for any set $X$ of $n$ points in the plane, and set $D$ of size $k$, there exists a subset $X' \subseteq X$ of size $|X'| \geq c_k |X|$ in which no pair of points is at some distance in $D$ (we say that $X'$ avoids distances in $D$). Such a set can be found efficiently. (B) (i) There is a subset of $X$ of size $n/2$ that avoids the maximum distance; this bound cannot be improved. (ii) There is a subset of $X$ of size $8n/47$ that avoids both the minimum and maximum distance; on the other hand, there exists $X$ such that at most $5n/16$ points can be retained with this property. (iii) There is a subset of $X$ of size $n/7$ whose diameter is at most half the original diameter; on the other hand, there exists $X$ such that at most $n/6$ points can be retained with this property. (C) (i) For any $\varepsilon>0$, a $(1-\varepsilon)$-approximation for \textsc{MIS} in the minimum distance graph of $n$ points in the plane can be found in $2^{O(1/\varepsilon)} n^{O(1)}$ time. (ii) Given a set $X$ of $n$ points in the plane, a maximum independent set in the graph of diameters can be computed in $O(n^2)$ time. The techniques used to handle the planar case can be extended to $\mathbf{R}^d$ for any fixed dimension $d$.

0.28

Euclidean Embeddings of Acyclic Hypergraph Line Metrics

cs.DM ·2026-10-19 ·Nicholas Popescu
theory similarity 0.65
Abstract

We study Euclidean embeddings of higher-order line metrics arising from hypergraphs. For a fixed threshold \(s\geq 1\), the \(s\)-line graph \(L_s(H)\) has one vertex for each hyperedge of \(H\), with two hyperedges adjacent when they intersect in at least \(s\) vertices; its shortest-path metric is the native \(s\)-line metric. In the unrestricted setting, every finite graph occurs as the \(s\)-line graph of some hypergraph, so the worst-case Euclidean distortion is \(Θ(\log n)\). We show that \(α\)-acyclicity yields a sharp improvement to \(Θ(\sqrt{\log\log n})\). Although the canonical join tree of an \(α\)-acyclic hypergraph may have arbitrarily large stretch relative to the native metric, we prove that for every \(s\), the \(s\)-line graphs of \(α\)-acyclic hypergraphs are exactly the dually chordal graphs. Using their constant-factor spanning-tree approximations together with classical tree-embedding bounds, we obtain an \(O(\sqrt{\log\log n})\) Euclidean embedding bound. We then show this is asymptotically tight by realizing every finite tree as the \(s\)-line graph of an \(α\)-acyclic hypergraph. Thus, the worst-case distortion is \(Θ(\sqrt{\log\log n})\), including for hypergraphs of rank at most \(3s+1\).

0.27