RUI: Embeddings of discrete metric spaces into Banach spaces

RUI：将离散度量空间嵌入到 Banach 空间中

• 批准号: 1201269
• 负责人: Mikhail Ostrovskii
• 金额: $ 15.34万
• 依托单位: Saint John's University
• 依托单位国家: 美国
• 项目类别: Standard Grant
• 财政年份: 2012
• 资助国家: 美国
• 起止时间: 2012-07-15 至 2016-02-29
• 项目状态: 已结题
• 来源: https://www.nsf.gov/awardsearch/showAward?AWD_ID=1201269&HistoricalAwards=false
• 关键词: RUI; Embeddings; discrete; metric; spaces

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.

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