权益分类	功能权益	普通用户	{{item.name}}会员
{{category.name}}	{{benefitItem.name}}

RUI: Embeddings of Discrete Metric Spaces into Banach Spaces

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

基本信息

批准号：
1700176
负责人：
Mikhail Ostrovskii
金额：
$ 17.8万
依托单位：
Saint John's University
依托单位国家：
美国
项目类别：
Continuing Grant
财政年份：
2017
资助国家：
美国
起止时间：
2017-07-01 至 2021-06-30
项目状态：
已结题

来源：
https://www.nsf.gov/awardsearch/showAward?AWD_ID=1700176&HistoricalAwards=false
关键词：
RUI Embeddings Discrete Metric Spaces

项目摘要

This project deals with embeddings of finite sets into spaces with well-understood geometry. Such embeddings form a well-established tool in theoretical computer science. Their usefulness can be seen in the following example: 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. One can subsequently employ algorithms available in computational geometry and tools from classical mathematics. In some cases one can even visualize the structure of the set, for example, see its clusters. Another application of embeddings is to construction of approximate algorithms in cases where the algorithms for finding the exact solution of a combinatorial optimization problem are not practical (consume too much time) and we seek not necessarily the optimal solution, but a solution that is close (in some sense) to being optimal. In many cases the best known approximate algorithms are based on metric embeddings. The project aims to deepen understanding in this important area.The main goal of the proposal is to study embeddings of discrete metric spaces into Banach spaces. The existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts, for example for applications in topology, weaker types of embeddings are useful, and even embeddings into high-dimensional or infinite-dimensional Banach spaces lead to important insights. This project will contribute to the following general question: 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 three main directions of the work are: (1) determine to what extent expanders and graphs with large girth resist nontrivially good embeddings; (2) find characterizations of well-known classes of Banach spaces in terms of embeddings; and (3) analyze structures that create obstructions to coarse embeddings of spaces with bounded geometry into a Hilbert space. The project is expected to employ a mixture of methods of geometric functional analysis and graph theory, with some use of methods of probability theory and geometric group theory.

这个项目涉及有限集合嵌入到具有良好理解的几何空间中。这种嵌入形成了理论计算机科学中的一个完善的工具。它们的有用性可以从下面的例子中看出：分析大量数据集在许多情况下都很重要。通常，数据被赋予其元素的自然距离（相异度）。分析这些数据集的有用方法之一是使用该集合的一些低失真嵌入到其结构众所周知的空间中，例如嵌入到二维或三维空间中。随后可以采用计算几何中可用的算法和经典数学中的工具。在某些情况下，甚至可以可视化集合的结构，例如，查看其聚类。嵌入的另一个应用是在寻找组合优化问题的精确解的算法不实用（消耗太多时间）的情况下构造近似算法，并且我们不一定要寻求最优解，而是寻求接近（在某种意义上）最优的解。在许多情况下，最著名的近似算法是基于度量嵌入。该项目旨在加深对这一重要领域的理解。该提案的主要目标是研究离散度量空间到Banach空间的嵌入。在实际应用中，低失真嵌入到平面中的情况相当少见。在许多情况下，例如在拓扑学中的应用，较弱类型的嵌入是有用的，甚至嵌入到高维或无限维Banach空间中也会产生重要的见解。这个项目将有助于以下一般性问题：找到新的类嵌入的有限和局部有限度量空间到Banach空间，并找到新的类型的障碍，这样的嵌入。工作的三个主要方向是：（1）确定在多大程度上具有大围长的扩张器和图抵抗非平凡的好嵌入;（2）找到著名的Banach空间类的嵌入特征;（3）分析结构，这些结构对有界几何空间到希尔伯特空间的粗嵌入造成障碍。该项目预计将采用几何泛函分析和图论的混合方法，并在一定程度上使用概率论和几何群论的方法。