RUI: Embeddings of discrete metric spaces into Banach spaces

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

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.