RUI: Embeddings of discrete metric spaces into Banach spaces

将离散度量空间嵌入到巴拿赫空间中是目前理论计算机科学和拓扑学中一个完善的工具。在理论计算机科学中，嵌入被用来构建，有时是最著名的，近似算法。在拓扑学中，用嵌入来证明Novikov猜想和Baum-Connes猜想的特殊情况。然而，关于嵌入的一些重要问题仍然没有解决。该项目的主要目的是在以下类型的问题上取得进展。确定在多大程度上，类膨胀体结构的存在是阻止几何有界空间粗糙嵌入希尔伯特空间的唯一障碍。确定具有大周长的展开器和图在多大程度上抵抗非平凡的良好嵌入。确定希尔伯特空间在多大程度上是最难嵌入的空间。找出众所周知的巴拿赫空间类的嵌入特征。在许多情况下，对大数据集的分析很重要。通常数据被赋予其元素之间的自然距离（不相似度）。分析这类数据集的一种有用的方法是将这些数据集的一些低失真嵌入到结构已知的空间中，例如二维或三维空间。在那之后，人们可以使用计算几何中可用的许多算法和来自微积分等经典数学部分的许多工具。在某些情况下，人们甚至可以可视化这个集合的结构，例如，看到它的簇。不幸的是，存在低失真嵌入到一个平面是相当罕见的应用。在许多情况下，弱得多（比低失真）的嵌入类型仍然是有用的，甚至嵌入到三维空间的高维或无限维推广中也会导致重要的结果。构建和分析这些嵌入是本提案的主要目标。

Embeddings of discrete metric spaces into Banach spaces is by now a well-established tool in Theoretical Computer Science and Topology. In Theoretical Computer Science embeddings are used to construct, sometimes the best known, approximation algorithms. In Topology embeddings are used to prove special cases of the Novikov conjecture and the Baum-Connes conjecture. Nevertheless, some of the important problems on embeddings remain open. The main purpose of the project is to achieve progress on problems of the following types. Determine to what extent presence of expander-like structures is the only obstruction to coarse embeddings of spaces with bounded geometry into a Hilbert space. Determine to what extent expanders and graphs with large girth resist nontrivially good embeddings. Determine to what extent the Hilbert space is the most difficult space to embed into. Find characterizations of well-known classes of Banach spaces in terms of embeddings.Analysis of large sets of data is important in many contexts. Usually data is endowed with a natural distance (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. After that one can use many algorithms available in computational geometry and many tools from such classical parts of mathematics as Calculus. In some cases one can even visualize the structure of the set, for example, see its clusters. Unfortunately the existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts much weaker (than low-distortion) types of embeddings are still useful, and even embeddings into high-dimensional or infinite-dimensional generalizations of the three-dimensional space lead to important results. Constructions and analysis of such embeddings is the main goal of the proposal.