Family 094Convex and metric geometryLeanNot yet digested

Subpolynomial dimension reduction in L $_{p}$

For every fixed

1\lt p\lt \infty

and distortion D > 1, every n-point subset of real L

_{p}

embeds into

\ell_p^d

with distortion at most D and dimension

d=n^{o(1)}

, answering Naor's sublinear-dimension question for p ≠ 2. In contrast, exact embeddings require worst-case dimension

\Theta(n^2)

when p ≠ 2.

Manuscripts in this family · 1

Sep 23, 2026·paper.pdfLean

For every fixed

1\lt p\lt \infty

and D > 1, every n-point subset of a real L

_{p}

space embeds into

\ell_p^d

with distortion at most D and subpolynomial dimension

d=n^{o(1)}

. The target has the same exponent p, and the embedding need not be linear.

Full abstract