Polynomial-dimensional embedding conjecture for finite subsets of 1\ell_1

Let M1\mathcal{M}\subseteq \ell_1 be a subset with M=n|\mathcal{M}|=n. An embedding of M\mathcal{M} into a normed space has distortion DD if distances are preserved up to a multiplicative factor with ratio DD. Embedding conjecture. Every nn-point subset of 1\ell_1 embeds with distortion O(1)O(1) into some normed space of dimension (logn)O(1)(\log n)^{O(1)}. This would improve the known lower-bound framework for dimensionality reduction into general normed spaces and would show that the lower bound of Matoušek cannot occur for subsets of 1\ell_1; the conjecture is presented as open.

Sources & referencesView supporting material

Primary source

Assaf Naor, “A spectral gap precludes low-dimensional embeddings”, arXiv:1611.08861 (2016).

Progress summary

Never refreshed

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Solutions 0

No solutions have been posted yet.