RUI: Embeddings of discrete metric spaces into Banach 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.