RUI: Embeddings of Discrete Metric Spaces into Banach Spaces

在许多情况下，分析大量数据集是很重要的。通常，数据被赋予其元素的自然距离或度量（相异度）。分析这类数据集的一种有用方法是将数据集嵌入到一个结构已知的空间中，例如二维或三维空间。更一般的空间被称为Banach空间。之后，人们可以使用计算几何中的许多算法和数学经典部分的许多工具，如微积分。 如果一个低失真嵌入到一个平面是可用的，人们甚至可以可视化的结构集;例如，它是可以看到它的集群。嵌入的另一个应用是构造近似算法。这意味着在用于找到组合优化问题的精确解的算法不实用的情况下（即，消耗太多的时间），我们不是在寻找最佳解决方案，而是在寻找接近（在某种意义上）最佳的解决方案。在许多情况下，最著名的精确解的近似算法是基于度量嵌入。这个项目的主要目标是研究嵌入到Banach空间的离散度量空间。这样的嵌入形成了理论计算机科学和拓扑学中的一个完善的工具。在实际应用中，低失真嵌入到平面中的情况相当少见。在许多情况下，较弱类型的嵌入仍然是有用的，甚至嵌入到高维或无限维的Banach空间导致重要的结果。PI将研究嵌入到Banach空间的离散度量空间。这个项目将有助于以下一般问题：找到新的类嵌入的有限和局部有限度量空间到Banach空间，并找到新类型的障碍，这样的嵌入。建议的主要工作方向是：1.研究图的可嵌入到不同类型的Banach空间、扩张和围长之间的关系。2.研究运输成本空间的几何性质，已知运输成本空间包含等距度量空间。3.找到著名的Banach空间类的嵌入特征。4.研究度量空间的可嵌入性与其部分的可嵌入性之间的关系。该方法预计将是几何功能分析和图论的方法的混合物，偶尔使用概率论和几何群论的方法。该奖项反映了NSF的法定使命，并已被认为是值得通过使用基金会的智力价值和更广泛的影响审查标准进行评估的支持。

Analysis of large sets of data is important in many contexts. Usually data is endowed with a natural distance or metric (degree of dissimilarity) of its elements. One of the useful approaches to analysis of such sets of data is to use some low-distortion embeddings of the set into a space whose structure is well-known; for example, into a two-dimensional or three-dimensional space. The more general spaces considered are called Banach spaces. After that one can use many algorithms available in computational geometry and many tools from classical parts of mathematics such as Calculus. If a low-distortion embedding into a plane is available, one can even visualize the structure of the set; for example, it is possible to see its clusters. Another application of embeddings is to construction of approximate algorithms. This means that in cases where the algorithms for finding the exact solution of a combinatorial optimization problem are not practical (i.e., consume too much time) we are looking not for the optimal solution, but for a solution close (in one or another sense) to being optimal. In many cases, the best known approximate algorithms for exact solutions are based on metric embeddings. The main goal of this project is to study embeddings of discrete metric spaces into Banach spaces. Such embeddings form a well-established tool in Theoretical Computer Science and Topology. The existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts, weaker types of embeddings are still useful, and even embeddings into high-dimensional or infinite-dimensional Banach spaces lead to important results. The PI will study embeddings of discrete metric spaces into Banach spaces. This project will contribute to the following general problem: Find new classes of embeddings of finite and locally finite metric spaces into Banach spaces and find new types of obstructions to such embeddings. The main directions of proposed work are: 1. Study relations between embeddability into different classes of Banach spaces, expansion, and girth of graphs. 2. Study geometric properties of transportation cost spaces, known to contain isometrically metric spaces on which they are built. 3. Find characterizations of well-known classes of Banach spaces in terms of embeddings. 4. Study relations between embeddability of metric spaces and embeddability of their parts. The methods are expected to be a mixture of methods of geometric functional analysis and graph theory, with occasional usage of methods of probability theory and geometric group theory.This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.