A subset of points in a metric space is said to "resolve" it if each other point is uniquely characterized by its distance to the points in the subset. Therefore, resolving sets can be used to represent points in abstract metric spaces as Euclidean vectors, and the smaller the size of the resolving set, the smaller the dimension of these vectors. Motivated by potential applications in natural language processing (NLP), in this talk, we address the resolvability 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 and highly likely and nearly optimal resolving sets of $(2^X,\text{Jac})$. This work was partially funded by the NSF grant No. 1836914.

Summary

Summary

Summary

Summary