A subset of points in a metric space is said to resolve it if every element in the space is uniquely determined by its distances from the points in the subset. Resolving sets thus enable the representation of points in abstract metric spaces as Euclidean vectors, with smaller resolving sets leading to lower-dimensional representations. The metric dimension of a space is the cardinality of its smallest resolving set.

Motivated by potential applications in natural language processing (NLP), this talk examines the resolvability and metric dimension of Jaccard spaces, i.e., metric spaces of the form $(2^X,\text{Jac})$, where $2^X$ is the power set of a finite but large set $X$, and $\text{Jac}$ is the Jaccard distance between subsets of $X$. In particular, we construct randomized resolving sets that, with high probability, are nearly optimal. Further details are available in the preprint arXiv:2405.11424.

This work was partially supported by NSF grant No. 1836914.