RUI: Embeddings of Discrete Metric Spaces into Banach Spaces

Saint John'S University, Jamaica NY

Investigators

Abstract

Analysis of large sets of data is important in many contexts. Usually data is endowed with a natural distance or metric (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. The more general spaces considered are called Banach spaces. After that one can use many algorithms available in computational geometry and many tools from classical parts of mathematics such as Calculus. If a low-distortion embedding into a plane is available, one can even visualize the structure of the set; for example, it is possible to see its clusters. Another application of embeddings is to construction of approximate algorithms. This means that in cases where the algorithms for finding the exact solution of a combinatorial optimization problem are not practical (i.e., consume too much time) we are looking not for the optimal solution, but for a solution close (in one or another sense) to being optimal. In many cases, the best known approximate algorithms for exact solutions are based on metric embeddings. The main goal of this project is to study embeddings of discrete metric spaces into Banach spaces. Such embeddings form a well-established tool in Theoretical Computer Science and Topology. The existence of a low-distortion embedding into a plane is rather rare in applications. In many contexts, weaker types of embeddings are still useful, and even embeddings into high-dimensional or infinite-dimensional Banach spaces lead to important results. The PI will study embeddings of discrete metric spaces into Banach spaces. This project will contribute to the following general problem: 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 main directions of proposed work are: 1. Study relations between embeddability into different classes of Banach spaces, expansion, and girth of graphs. 2. Study geometric properties of transportation cost spaces, known to contain isometrically metric spaces on which they are built. 3. Find characterizations of well-known classes of Banach spaces in terms of embeddings. 4. Study relations between embeddability of metric spaces and embeddability of their parts. The methods are expected to be a mixture of methods of geometric functional analysis and graph theory, with occasional usage of methods of probability theory and geometric group theory. This award reflects NSF's statutory mission and has been deemed worthy of support through evaluation using the Foundation's intellectual merit and broader impacts review criteria.